#include <iostream>#include <cstring>#include <cstdio>#define maxn 1010#define maxm 55555using namespace std;const int inf=maxn;int to[maxm],cap[maxm],cost[maxm],next[maxm],first[maxn],edge;int d[maxn],num[maxn],from[maxn],tag[maxn],TAG=222;int Q[maxm],bot,top;int n,m,s,t,ans,T,a[maxn];void _init(){    edge=-1,s=0,t=n+1,ans=0;    for (int i=s; i<=t; i++) first[i]=-1;}void addedge(int U,int V,int W,int C){    edge++;    to[edge]=V,cap[edge]=W,cost[edge]=C,next[edge]=first[U],first[U]=edge;    edge++;    to[edge]=U,cap[edge]=0,cost[edge]=-C,next[edge]=first[V],first[V]=edge;}bool bfs(){    Q[bot=top=1]=s,d[s]=0,num[s]=inf,from[s]=-1,tag[s]=++TAG;    while (bot<=top){        int cur=Q[bot++];        for (int i=first[cur]; i!=-1; i=next[i])            if (cap[i]>0 && (tag[to[i]]!=TAG || d[cur]+cost[i]<d[to[i]])){                d[to[i]]=d[cur]+cost[i];                tag[to[i]]=TAG,                num[to[i]]=min(num[cur],cap[i]);                Q[++top]=to[i];                from[to[i]]=i;            }    }    if (tag[t]!=TAG || num[t]<=0) return false;    ans+=num[t]*d[t];    for (int i=t; from[i]!=-1; i=to[from[i]^1])        cap[from[i]]-=num[t],cap[from[i]^1]+=num[t];    return true;}int main(){    scanf("%d",&T);    while (T--)    {        scanf("%d",&n);        _init();        for (int i=1; i<=n; i++) {            scanf("%d",&a[i]);            addedge(s,i,a[i],0);            addedge(i,t,1,0);            if (i<n) addedge(i,i+1,inf,1);            if (i>1) addedge(i,i-1,inf,1);        }        addedge(1,n,inf,1);        addedge(n,1,inf,1);        while (bfs()) ;        printf("%d\n",ans);    }    return 0;}