/**
 *    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 = 1 << 18;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 7;

int a[N];
int used[N];
int n;

int tmin[2 * N];
int tmax[2 * N];

int SZ;

int getmin(int L, int R)
{
    int res = L;
    L += SZ;
    R += SZ;
    while (L <= R)
    {
        if ((L & 1) == 1 && a[res] > a[tmin[L]]) res = tmin[L];
        if ((R & 1) == 0 && a[res] > a[tmin[R]]) res = tmin[R];
        L = (L + 1) >> 1;
        R = (R - 1) >> 1;
    }
    return res;
}

int getmax(int L, int R)
{
    int res = L;
    L += SZ;
    R += SZ;
    while (L <= R)
    {
        if ((L & 1) == 1 && a[res] < a[tmax[L]]) res = tmax[L];
        if ((R & 1) == 0 && a[res] < a[tmax[R]]) res = tmax[R];
        L = (L + 1) >> 1;
        R = (R - 1) >> 1;
    }
    return res;
}

void updmin(int x)
{
    x += SZ;
    while (x > 1)
    {
        x >>= 1;
        if (a[tmin[2 * x]] < a[tmin[2 * x + 1]]) tmin[x] = tmin[2 * x];
        else tmin[x] = tmin[2 * x + 1];
    }
}
void updmax(int x)
{
    x += SZ;
    while (x > 1)
    {
        x >>= 1;
        if (a[tmax[2 * x]] > a[tmax[2 * x + 1]]) tmax[x] = tmax[2 * x];
        else tmax[x] = tmax[2 * x + 1];
    }
}


void DO(int x, int y, int cnt)
{
    a[x] -= cnt;
    a[y] -= cnt * 2;
    updmin(x);
    updmin(y);
    updmax(x);
    updmax(y);
}   

ll solve()
{
    ll original_sum = 0;
    forn(i, n) original_sum += a[i];
    
    SZ = 1;
    while (SZ < n) SZ *= 2;

    forn(i, 2 * SZ) tmin[i] = tmax[i] = 0;

    forn(i, n) tmin[SZ + i] = tmax[SZ + i] = i;
    for (int i = SZ - 1; i > 0; --i)
    {
        if (a[tmin[2 * i]] < a[tmin[2 * i + 1]]) tmin[i] = tmin[2 * i];
        else tmin[i] = tmin[2 * i + 1];
        if (a[tmax[2 * i]] > a[tmax[2 * i + 1]]) tmax[i] = tmax[2 * i];
        else tmax[i] = tmax[2 * i + 1];
    }

    forn(i, n) used[i] = 0;

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

    ll res = 0;
    int cntused = 0;
    while (1)
    {
        int pos1 = getmin(0, n - 1);
        int pos2 = getmax(0, n - 1);
        pi small = {a[pos1], pos1};
        pi large = {a[pos2], pos2};
        if (small.F < 0)
        {
            return 0;
        }
        if (small.F == large.F) return (original_sum - 3 * res) / n;
        if (used[large.S] == 0)
        {
            used[large.S] = 1;
            cntused++;
        }
        if (cntused == n)
        {
            return 0;
        }
        int gap = large.F - small.F;
        int x = (large.S + n - 1) % n;
        int y = large.S;
        int z = (large.S + 1) % n;
        int cnt = max(1, (gap - (a[z] - small.F) / 2) / 2);
        

        DO(x, y, cnt);
        res += cnt;
    }
}


int main()
{
    #ifdef home
        assert(freopen("in", "r", stdin));
        // assert(freopen("out", "w", stdout));
    #endif
    if (0)
    {
        n = 2e5;
        mt19937 rnd;
        int X = 1e8;
        forn(i, n) a[i] = rnd() % (X) +  5* X;
        ll res = solve();
        printf("%lld\n", res);
    }
    else
    {
        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;
}