/**
 *    author:  [itmo] enot110
 *    created: 2024-11-10 14:11:50
**/
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define pw(x) (1LL<<(x))

using namespace std;

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = 1.01e9;
const dbl eps = 1e-9;

/* --- main part --- */

struct pt
{
    ll x, y;
    pt(){}
    pt(ll xx, ll yy): x(xx), y(yy) {}
    void read() { scanf("%lld%lld", &x, &y); }
};

inline pt operator + (pt p1, pt p2) { return pt(p1.x + p2.x, p1.y + p2.y); }
inline pt operator - (pt p1, pt p2) { return pt(p1.x - p2.x, p1.y - p2.y); }
inline pt operator * (pt p, ll c) { return pt(p.x * c, p.y * c); }
inline pt operator * (ll c, pt p) { return pt(p.x * c, p.y * c); }

inline bool operator == (pt p1, pt p2) { return p1.x == p2.x && p1.y == p2.y; }
inline bool operator != (pt p1, pt p2) { return p1.x != p2.x || p1.y != p2.y; }

inline dbl len(pt p) { return sqrt(p.x * p.x + p.y * p.y); }
inline ll len2(pt p) { return p.x * p.x + p.y * p.y; }
inline dbl dist(pt p1, pt p2) { ll dx = p1.x - p2.x; ll dy = p1.y - p2.y; return sqrt(dx * dx + dy * dy); }
inline ll dist2(pt p1, pt p2) { ll dx = p1.x - p2.x; ll dy = p1.y - p2.y; return dx * dx + dy * dy; }
inline ll scal(pt p1, pt p2) { return p1.x * p2.x + p1.y * p2.y; }
inline ll vect(pt p1, pt p2) { return p1.x * p2.y - p1.y * p2.x; }
inline bool operator < (pt p1, pt p2) { return p1.x < p2.x || (p1.x <= p2.x && p1.y < p2.y); }

const int N = 2e5 + 10;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 7;

int a[N];
int n;
set<pi> S;

void DO(int x, int cnt)
{
    int y = (x + 1) % n;
    S.erase({a[x], x});
    S.erase({a[y], y});
    a[x] -= cnt;
    a[y] -= cnt * 2;
    S.insert({a[x], x});
    S.insert({a[y], y});
}   

ll solve()
{
    ll original_sum = 0;
    forn(i, n) original_sum += a[i];
    
    S.clear();
    forn(i, n) S.insert({a[i], i});

    ll sum = 0;
    forn(i, n) sum += a[i];
    if (n % 3 == 0 && sum % 3 != 0) return 0;

    ll res = 0;
    while (1)
    {
        pi small = *S.begin();
        pi large = *S.rbegin();
        if (small.F < 0) return 0;
        if (small.F == large.F) return (original_sum - 3 * res) / n;
        int gap = large.F - small.F;
        int cnt = max(1, gap / 4);
        DO((large.S + n - 1) % n, cnt);
        res += cnt;
    }
}


int main()
{
    #ifdef home
        assert(freopen("in", "r", stdin));
        // assert(freopen("out", "w", stdout));
    #endif
    int tn;
    scanf("%d", &tn);
    forn(tt, tn)
    {
        scanf("%d", &n);
        forn(i, n) scanf("%d", &a[i]);

        ll res = solve();
        printf("%lld\n", res);
    }




    #ifdef home
        eprintf("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif
    return 0;
}