/* -----------------------
Autor: Tomasz Boguslawski
-------------------------- */
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
#include<sstream>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include <fstream>
#include<math.h>

#define LL long long
#define FOR(x, b, e) for(LL x = b; x <= (e); x++)
#define FORS(x, b, e, s) for(LL x = b; x <= (e); x+=s)
#define FORD(x, b, e) for(LL x = b; x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG if (debug)
#define MIN(a,b) ((a>b)?b:a)
#define MAX(a,b) ((a>b)?a:b)

//#include<random>

using namespace std;


//random_device dev;
//mt19937 rng(dev());


LL n2[1100000];
LL n3[1100000];

const LL M=210000;

LL n;
LL a[210000];
LL b[210000];


void init()
{
    FOR(i,0,2) n3[i]=0;
    n3[3]=1;
    FOR(i,4,1000) n3[i]=(i*n3[i-1])/(i-3);
    n2[0]=0; n2[1]=0; n2[2]=1;
    FOR(i,3,1000) n2[i]=(i*n2[i-1])/(i-2);
}

// wektor res: dla zadanej liczby mieszkancow, ile potrzeba na prawo
// ale wartosc -1 oznacza, ze nie moze byc taka liczba mieszkancow

bool lastOKis0;

void calcForFirst(LL* res, LL r, LL B, LL &lastOK, LL &firstOK)
{
    if (r==0)
    {
        // domek nr 1 nie potrzebuje niczego, zadnych wymagan
        // niezaleznie od tego, ile ma mieszkancow
        //FOR(u,0,M) res[u]=0;
        firstOK=0; lastOK=0;
        return;
    }
    // r>0
    res[0] = -1; res[1] = -1; // musi byc co najmniej 2 mieszkancow
    firstOK=2;
    lastOKis0=false;
    FOR(u,2,M)
    {
        LL licz = r - n3[u];
        LL mian = n2[u];
        if (licz<=0) res[u] = 0;
        else
        {
            LL dziel = licz/mian;
            LL w = dziel;
            if (w*mian<licz) w++;
            res[u]=w;
        }
        if (res[u]==0) { lastOK=u; lastOKis0=true; break; }
    }
    if (lastOK>B) { lastOK=B; lastOKis0=false; }
}

void calcForNext(LL r, LL B, LL* vp, LL* res, LL &lastOKvp, LL &firstOKvp, LL &lastOK, LL &firstOK)
{
    firstOK=-1;
    lastOK=0;
    //FOR(t,firstOKvp,lastOKvp+B)
    lastOKis0=false;
    LL v;
    FOR(t,firstOKvp,lastOKvp+B)
    {
        //cout << "trying t=" << t << "\n";
        LL minW = 1000000000;
        LL firstU=MAX(1,t-lastOKvp);
        //LL v=t-firstU;
        FOR(u, firstU , MIN(B,t-firstOKvp))
        {
            //cout << "  trying u=" << u << "\n";
            v = t-u;
            //LL rv = 0;
            //LL rv=vp[v];
            //if (v<=lastOKvp) rv=vp[v]; else continue; //rv=1000000000;

            // w domu jest "u" mieszkancow i wymagamy r turniejow
            // po lewo mamy "v" mieszkancow i wymagamy rv mieszkancow
            //if (rv==-1) break; // nie moze byc v mieszkancow po lewo w ogole, a bedzie tylko gorzej
            LL req1 = vp[v]-u; // co najmniej tyle musi byc ze wzgledu na domki po lewo
            //cout << "  req1=" << req1 << "\n";
            //cout << "t=" << t << "v=" << v << " u=" << u << " req1=" << req1 << "\n"; cout.flush();
            LL licz = r - n3[u] - v*n2[u];
            LL w=-1;
            if (licz<=0) w=0;
            else
            {
                LL mian = n2[u] + u*v;
                //if (mian==0) continue;// w=-1;
                //else
                //{
                w = 1 + ((licz-1)/mian);
                //    LL dziel = licz/mian;
                //    if (dziel*mian<licz) dziel++;
                //    w = dziel;
                //}
            }
            // "w" - ile minimalnie mieszkancow musi byc po prawo, zeby spelnic wymagania biezacego domku
            /*
            if (w==-1)
            {
                //cout << " nie da sie\n";
                continue; // nie da sie w ogole
            }
            */
            //w = MAX(w, req1); // jesli biezacy domek potrzebuje minimum 3, ale wczesniejsze potrzebuja 8, to jest potrzebne 8
            if (req1>w) w=req1;
            //cout << "  w=" << w << "\n";
            if (w<minW) minW=w;
        }
        if (minW==1000000000) minW=-1;
        //cout << "   minW=" << minW << "\n";
        res[t]=minW;
        if (firstOK==-1 && res[t]!=-1) firstOK=t;
        if (res[t]!=-1) lastOK=t;
        if (res[t]==0) { lastOK=t; lastOKis0=true; break; }
    }
}

LL calc()
{
    if (n==0) return 0;
    LL* v1 = new LL[M+1];
    LL* v2 = new LL[M+1];
    LL* pom;
    LL first0v1=-1; LL firstOKv1=-1;
    LL first0v2=-1; LL firstOKv2=-1;
    calcForFirst(v1, a[1], b[1], first0v1, firstOKv1);
    //cout << "first0=" << first0v1 << " firstOK=" << firstOKv1 << "\n";
    //FOR(i,firstOKv1,first0v1) { cout << " " << i << ": " << v1[i] << "\n"; if (v1[i]==0) break; }
    //cout << "LastOKis0: " << lastOKis0 << "\n";
    //cout.flush();
    FOR(d,2,n)
    {
        //cout << "--- calculating for d=" << d << "\n";
        calcForNext(a[d],b[d],v1,v2,first0v1,firstOKv1, first0v2, firstOKv2);
        pom=v1; v1=v2; v2=pom;
        first0v1=first0v2; firstOKv1=firstOKv2;
        //cout << "---- for d=" << d << " first0=" << first0v1 << "\n";
        //FOR(i,firstOKv1,first0v1) { cout << " " << i << ": " << v1[i] << "\n"; if (v1[i]==0) break; }
        //cout << "LastOKis0: " << lastOKis0 << "\n";

    }
    //cout << "--- Final:\n";
    //cout << "firstOK=" << firstOKv1 << " first0=" << first0v1 << "\n";
    //FOR(i,0,first0v1) cout << i << ": " << v1[i] << "\n";
    delete [] v1;
    delete [] v2;
    if (lastOKis0) return first0v1; else return first0v1+1;
}

LL man[100];

bool brutTry(LL pos, LL m)
{
    if (pos>n)
    {
        //FOR(i,1,n) cout << man[i] << " ";
        //cout << " | ";
        LL poLewo=0;
        LL poPrawo=0; FOR(i,2,n) poPrawo+=man[i];
        bool ok=true;
        FOR(i,1,n)
        {
            // ile turniejow mozna rozegrac w domku "i":
            LL u = man[i];
            LL ile=n3[u] + n2[u]*(poLewo+poPrawo) + u*poLewo*poPrawo;
            //cout << ile << " ";
            if (ile<a[i]) { ok=false; break; }
            poLewo += u;
            poPrawo -= man[i+1];
        }
        //cout << "\n";
        return ok;
    }
    else if (pos==n)
    {
        man[pos] = m;
        bool ok=brutTry(pos+1, 0);
        man[pos] = 0;
        if (ok) return ok;
    }
    else
    {
        FORD(i,m,0)
        {
            man[pos]=i;
            bool ok=brutTry(pos+1, m-i);
            if (ok) return ok;
        }
    }
    return false;
}

bool brutOK(LL m)
{
    // rozmieszczam m osob na wszystkie mozliwe sposoby:
    //cout << "Probuje: " << m << " ludzi.\n";
    FOR(i,1,n) man[i]=0;
    return brutTry(1,m);
}

LL brut()
{
    FOR(m,0,1000) if (brutOK(m)) return m;
    return -1;
}


/*
uniform_int_distribution<mt19937::result_type> dist(0,1000000000);

void prepareRandomData(LL upTo)
{
    FOR(i,1,n) a[i]=1+dist(rng)%upTo;
}
*/


void removeZeroes()
{
    LL non=0;
    FOR(i,1,n) if (a[i]!=0) { non++; a[non]=a[i]; }
    n=non;
}

void calcB()
{
    LL non0=0; FOR(i,1,n) if (a[i]>0) non0++;
    LL left=0; LL right=non0; if (a[1]>0) right--;
    LL minimumSocjalne=0;
    FOR(d,1,n)
    {
        //cout << d << ": left=" << left << " right=" << right << "\n";
        FOR(k,0,200)
        {
            minimumSocjalne=n3[k]+n2[k]*(left+right)+k*left*right;
            if (minimumSocjalne>=a[d]) { b[d]=k; break; }
        }
        if (a[d]!=0) left++;
        if (a[d+1]!=0) right--;
    }
}

LL* calcForFirstOrig(LL r, LL &first0, LL &firstOK)
{
    LL* res = new LL[M+1];
    if (r==0)
    {
        // domek nr 1 nie potrzebuje niczego, zadnych wymagan
        // niezaleznie od tego, ile ma mieszkancow
        //FOR(u,0,M) res[u]=0;
        firstOK=0; first0=0;
        return res;
    }
    // r>0
    res[0] = -1; res[1] = -1; // musi byc co najmniej 2 mieszkancow
    firstOK=2;
    FOR(u,2,M)
    {
        LL licz = r - n3[u];
        LL mian = n2[u];
        if (licz<=0) res[u] = 0;
        else
        {
            LL dziel = licz/mian;
            LL w = dziel;
            if (w*mian<licz) w++;
            res[u]=w;
        }
        if (res[u]==0) { first0=u; break; }
    }
    return res;
}

LL* calcForNextOrig(LL r, LL* vp, LL &first0vp, LL &firstOKvp, LL &first0, LL &firstOK)
{
    LL* res = new LL[M+1];
    firstOK=-1;
    FOR(t,firstOKvp,M)
    {
        LL minW = 1000000000;
        FOR(u,0,MIN(t,200))
        {
            LL v = t-u;
            LL rv = 0; if (v<firstOKvp) rv=-1; else if (v<first0vp) rv=vp[v]; else rv=0;
            // w domu jest "u" mieszkancow i wymagamy r turniejow
            // po lewo mamy "v" mieszkancow i wymagamy rv mieszkancow
            if (rv==-1) continue; // nie moze byc v mieszkancow po lewo w ogole
            LL req1 = rv-u; // co najmniej tyle musi byc ze wzgledu na domki po lewo
            //cout << "t=" << t << "v=" << v << " u=" << u << " req1=" << req1 << "\n"; cout.flush();
            LL licz = r - n3[u] - v*n2[u];
            LL mian = n2[u] + u*v;
            LL w=-1;
            if (licz<=0) w=0;
            else
            {
                if (mian==0) w=-1;
                else
                {
                    LL dziel = licz/mian;
                    if (dziel*mian<licz) dziel++;
                    w = dziel;
                }
            }
            // "w" - ile minimalnie mieszkancow musi byæ po prawo, zeby spelnic wymagania biezacego domku
            if (w==-1) continue; // nie da sie w ogole
            w = MAX(w, req1); // jesli biezacy domek potrzebuje minimum 3, ale wczesniejsze potrzebuja 8, to jest potrzebne 8
            if (w<minW) minW=w;
        }
        if (minW==1000000000) minW=-1;
        res[t]=minW;
        if (firstOK==-1 && res[t]!=-1) firstOK=t;
        if (res[t]==0) { first0=t; break; }
    }
    return res;
}

LL calcOrig()
{
    LL* v1;
    LL* v2;
    LL first0v1=-1; LL firstOKv1=-1;
    LL first0v2=-1; LL firstOKv2=-1;
    v1=calcForFirstOrig(a[1], first0v1, firstOKv1);
    //cout << "first0=" << first0v1 << " firstOK=" << firstOKv1 << "\n";
    //FOR(i,0,M) { cout << " " << i << ": " << v1[i] << "\n"; if (v1[i]==0) break; }
    FOR(d,2,n)
    {
        v2=calcForNextOrig(a[d],v1,first0v1,firstOKv1, first0v2, firstOKv2);
        delete [] v1;
        v1=v2; first0v1=first0v2; firstOKv1=firstOKv2;
        //cout << "--- for d=" << d << " first0=" << first0v1 << "\n";
        //FOR(i,firstOKv1,M) { cout << " " << i << ": " << v1[i] << "\n"; if (v1[i]==0) break; }
    }
    //cout << "--- Final:\n";
    //cout << "firstOK=" << firstOKv1 << " first0=" << first0v1 << "\n";
    //FOR(i,0,first0v1) cout << i << ": " << v1[i] << "\n";
    delete [] v1;
    return first0v1;
}



/// MAIN
int main(int argc, char* argv[])
{
    // magic formula, which makes streams work faster:
	ios_base::sync_with_stdio(0);

	//cout << "Started...\n"; cout.flush();
	init();

    /*
	FOR(q,1,1000000)
	{
	    n=4000;
        prepareRandomData(1000000);
        //FOR(i,1,n) cout << a[i] << " "; cout << "\n"; cout.flush();
        //LL c0=calcOrig();
        removeZeroes();
        //FOR(i,1,n) cout << a[i] << " "; cout << "\n"; cout.flush();
        calcB();
        //FOR(i,1,n) cout << b[i] << " "; cout << "\n";
        //LL c1=calcOrig();
        LL c2=calc(); LL c0=c2;
        cout << c0 << " " << c2 << "\n"; cout.flush();
        if (c0!=c2) { cout << "Error!\n"; return 0; }
	}
	return 0;
    */

    /*
    cout << "Started...\n"; cout.flush();
	n=200000;
	FOR(d,1,n) a[d]=1000000;
	//prepareRandomData(20);
	//cout << calcOrig() << "\n";
	removeZeroes();
	calcB();
	//a[20]=1000000;
	//FOR(d,1,n) a[d]=1000000;
	//prepareRandomData();
	//cout << calcOrig() << "\n"; cout.flush();
	cout << calc() << "\n";
    return 0;
    */

	LL t; cin >> t;
	FOR(z,1,t)
	{
	    cin >> n;
	    FOR(i,1,n) cin >> a[i];
	    removeZeroes();
	    calcB();
	    cout << calc() << "\n";
	}
	return 0;
}