#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500010,inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t,x,y,z,vi,T;
int v[N],w[N],d[N];
int ans,sum,h[N];
int pre[N],nxt[N];
int id;int q[N];
void add(int x,int y,int z,int vi){
	v[id]=y;w[id]=z;d[id]=vi;
	nxt[id]=pre[x];pre[x]=id++;
}
int now[N],book[N];
bool bfs(){
	memset(h,0x3f,sizeof(h));
	memset(book,0,sizeof(book));
	
	int head=0,tail=0;
	q[tail++]=s;
	book[s]=1;
	h[s]=0;
	now[s]=pre[s];
	while(head<tail){
		int l=q[head];
		head++;
       book[l]=0;
		for(int i=pre[l];i!=-1;i=nxt[i]){
			if(w[i]&&h[v[i]]>h[l]+d[i]){
				h[v[i]]=h[l]+d[i];
				now[v[i]]=pre[v[i]];
				if(book[v[i]]==0){
					book[v[i]]=1;
					q[tail++]=v[i];
				}
			}
		} 
	}
	return h[t]!=inf;
}
int dinic(int x,int flow){
	if(x==t)return flow;
	int res=0,k;
	book[x]=1;
	for(int i=now[x];flow&&i!=-1;i=nxt[i]){
        now[x]=i;
		if(!book[v[i]]&&w[i]>0&&h[v[i]]==h[x]+d[i]){
			k=dinic(v[i],min(w[i],flow));
			if(k==0)h[v[i]]=inf;
			res+=k;
			flow-=k;
			w[i]-=k;
			w[i^1]+=k;
			sum+=d[i]*k;
		}
	}
    book[x]=0;
    return res;
}
signed main(){
    cin>>T;
    while(T--){
        memset(v,0,sizeof(v));
        memset(w,0,sizeof(w));
        memset(d,0,sizeof(d));
        memset(pre,-1,sizeof(pre));
        memset(nxt,0,sizeof(nxt));
        id=0;
        cin>>n;
        s=0;t=n+1;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            add(s,i,x,0);
            add(i,s,0,0);
            add(i,t,1,0);
            add(t,i,0,0);
        }
        for(int i=1;i<=n;i++){
            int previouS=i-1,nexT=i+1;
            if(previouS==0)previouS=n;
            if(nexT==n+1)nexT=1;
            add(i,nexT,inf,1);
            add(nexT,i,0,-1);
            add(i,previouS,inf,1);
            add(previouS,i,0,-1);
        }
        while(bfs())dinic(s,inf);
        cout<<sum<<"\n";
    }
	return 0;
}