#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define sigma signed

#define int long long
#define forn(i,n) for(int i=0; i<n; ++i)

void solve() {
    int n; cin>>n;
    vector<int> a(n); forn(i,n) cin>>a[i];
    int original_sum = 0;
    forn(i,n) original_sum += a[i];
    int ans=1e18;
    int ok=1; forn(i,n) ok&=a[i]==a[0];
    if (ok) ans=0;
    int mn=1e18;
    forn(i,n) mn=min(mn,a[i]); 
    forn(r,min(3ll,mn+1)) {
        vector<int> x(n),y(n);
        forn(i,n) {
            x[i]=(a[i]-r)&1;
            y[(i+1)%n]=x[i];
        }
        for(int j=0; j<40; ++j) {
            int m=(4ll<<j)-1;
            forn(i,n) {
                x[i] = (a[i]-2*y[i]-r)&m;
            }
            forn(i,n) {
                y[(i+1)%n]=x[i];
            }
            //out<<"! "<<r<<":\n";
            //forn(i,n) cout<<x[i]<<' '; cout<<'\n';
            //forn(i,n) cout<<y[i]<<' '; cout<<'\n';
        }
        //cout<<"! "<<r<<":\n";
        //forn(i,n) cout<<x[i]<<' '; cout<<'\n';
        //forn(i,n) cout<<y[i]<<' '; cout<<'\n';
        int bad=0;
        forn(i,n) {
            int z = a[i]-x[i]-2*y[i];
            if (z < 0 || z!=r) bad=1;
        }
        if (bad) continue;
        int sum=0; forn(i,n) sum+=x[i];
        int d=1e18; forn(i,n) d=min(d,x[i]);
        sum-=d*n;
        ans=min(ans,sum);
    }
    cout<<(ans==1e18?0:(original_sum-3*ans)/n)<<'\n';

}   

sigma main() {
    int t; cin>>t;
    while (t--) solve();
}
