#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;

//#define DEBUG(x) x
//#define CALC_TIME

#ifndef DEBUG
    #define DEBUG(x)
#endif

#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) auto x = (n)
#define FOREACH(x,c) for(VAR(x, (c).begin()); x != (c).end(); ++x)
#define CONTAINS(x,elem) ((x).find(elem) != (x).end())

const int MAX_N = 200002;

int input[MAX_N];

constexpr int newton3(int number) {
    if (number >= 3) {
        return number*(number-1)*(number-2)/6;
    } else {
        return 0;
    }
}
constexpr int newton2(int number) {
    if (number >= 2) {
        return number * (number-1)/2;
    } else {
        return 0;
    }
}

const int NEWTON3_SIZE = 184;
int newton3Tab[NEWTON3_SIZE] = {0, 0, 0, 3, 4, 10, 20, 35, 56, 84, 
	120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 
	1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654, 
	4060, 4495, 4960, 5456, 5984, 6545, 7140, 7770, 8436, 9139, 
	9880, 10660, 11480, 12341, 13244, 14190, 15180, 16215, 17296, 18424, 
	19600, 20825, 22100, 23426, 24804, 26235, 27720, 29260, 30856, 32509, 
	34220, 35990, 37820, 39711, 41664, 43680, 45760, 47905, 50116, 52394, 
	54740, 57155, 59640, 62196, 64824, 67525, 70300, 73150, 76076, 79079, 
	82160, 85320, 88560, 91881, 95284, 98770, 102340, 105995, 109736, 113564, 
	117480, 121485, 125580, 129766, 134044, 138415, 142880, 147440, 152096, 156849, 
	161700, 166650, 171700, 176851, 182104, 187460, 192920, 198485, 204156, 209934, 
	215820, 221815, 227920, 234136, 240464, 246905, 253460, 260130, 266916, 273819, 
	280840, 287980, 295240, 302621, 310124, 317750, 325500, 333375, 341376, 349504, 
	357760, 366145, 374660, 383306, 392084, 400995, 410040, 419220, 428536, 437989, 
	447580, 457310, 467180, 477191, 487344, 497640, 508080, 518665, 529396, 540274, 
	551300, 562475, 573800, 585276, 596904, 608685, 620620, 632710, 644956, 657359, 
	669920, 682640, 695520, 708561, 721764, 735130, 748660, 762355, 776216, 790244, 
	804440, 818805, 833340, 848046, 862924, 877975, 893200, 908600, 924176, 939929, 
	955860, 971970, 988260, 1004731
};

int findNewton3ForResult(int input) {
    auto pos = upper_bound(newton3Tab, newton3Tab+NEWTON3_SIZE, input-1 /* upper_bound find position AFTER value */);
    return pos-newton3Tab;
}

struct Score {
    int minLeft;
    int minRight;
}
scores[MAX_N];

int sumMinParticipants(int from, int to, int n) {
    if (from>to) {
        return 0;
    } else {
        return to-from+1 + (from==0 ? 1 : 0) + (to==n-1 ? 1 : 0);
    }
}

int participantsTree[MAX_N * 2];
int treeHeaderSize;

void buildTree(int n) {
    REP(x,treeHeaderSize)
        participantsTree[x] = 0;
    for(int i=treeHeaderSize+n-1;i>1;--i) {
        participantsTree[i/2] += participantsTree[i];
    }
}
int getTreeSum(int fromInclusive, int toInclusive) {
    if (fromInclusive > toInclusive) {
        return 0;
    }
    int startIndex = fromInclusive + treeHeaderSize;
    int endIndex = toInclusive + treeHeaderSize;
    if (fromInclusive == toInclusive) {
        return participantsTree[startIndex];
    }
    int result = participantsTree[startIndex] + participantsTree[endIndex];
    while(startIndex < endIndex-1) {
        if (endIndex & 1)
            result += participantsTree[endIndex-1];
        if (!(startIndex&1))
            result += participantsTree[startIndex+1];
        endIndex >>= 1;
        startIndex >>= 1;
    }
    return result;
}
void addTree(int index, int value) {
    int valueIndex = index + treeHeaderSize;
    while(valueIndex != 0) {
        participantsTree[valueIndex] += value;
        valueIndex >>= 1;
    }
}

void printTree(int realN) {
    for(int x=1;x<treeHeaderSize+realN;++x) {
        cerr<<participantsTree[x]<<" ";
    }
    cerr<<endl;
}

long long calcTournamentsLimit(int pos, int n) {
    long long leftTree = getTreeSum(0, pos-1);
    long long rightTree = getTreeSum(pos+1, n-1);
    long long hereTree = getTreeSum(pos, pos);
//    DEBUG(cerr<<"calcTournamentLimit("<<pos<<") = "<<leftTree<<"/"<<hereTree<<"/"<<rightTree<<"="<<(leftTree*hereTree*rightTree)<<"+"<<((leftTree+rightTree)*newton2(hereTree))<<"+"<<newton3(hereTree)<<endl;);
    return leftTree*hereTree*rightTree + (leftTree+rightTree)*newton2(hereTree)+newton3(hereTree);
}

void addParticipantsFromEdges(int realN) {
    int firstUnsatisfied=0, lastUnsatisfied=realN-1;
    while (firstUnsatisfied <= lastUnsatisfied) {
        long long maxTournamentFirst, maxTournamentLast;
        while(firstUnsatisfied <= lastUnsatisfied) {
            maxTournamentFirst = calcTournamentsLimit(firstUnsatisfied, realN);
            if (maxTournamentFirst >= input[firstUnsatisfied]) {
                DEBUG(cerr<<"satisfied first "<<firstUnsatisfied<<" ("<<maxTournamentFirst<<"/"<<input[firstUnsatisfied]<<")"<<endl;)
                ++firstUnsatisfied;
                continue;
            } else {
                break;
            }
        }
        while(firstUnsatisfied <= lastUnsatisfied) {
            maxTournamentLast = calcTournamentsLimit(lastUnsatisfied, realN);
            if (maxTournamentLast >= input[lastUnsatisfied]) {
                DEBUG(cerr<<"satisfied last "<<lastUnsatisfied<<" ("<<maxTournamentLast<<"/"<<input[lastUnsatisfied]<<")"<<endl;)
                --lastUnsatisfied;
                continue;
            } else {
                break;
            }
        }
        if (firstUnsatisfied > lastUnsatisfied) {
            break;
        }
        DEBUG(cerr<<"missing "<<(input[firstUnsatisfied]-maxTournamentFirst)<<" at first and " << (input[lastUnsatisfied]-maxTournamentLast) << " at last" << endl;)
        if ((input[firstUnsatisfied]-maxTournamentFirst) > (input[lastUnsatisfied]-maxTournamentLast) ) {
            DEBUG(cerr<<"increase first "<<firstUnsatisfied<<endl;)
            addTree(firstUnsatisfied, 1);
        } else {
            DEBUG(cerr<<"increase last "<<lastUnsatisfied<<endl;)
            addTree(lastUnsatisfied, 1);
        }
    }
}

void addParticipantsFromBiggestDifference(int n) {
    //map [missingTournaments -> [totalParticipants, houseNo]]
    struct HouseStats {
        int houseNo;
        int missingTournaments;
        int totalParticipantsForCalculation;
        bool operator<(const HouseStats& other) const {
            return 
                missingTournaments != other.missingTournaments ? missingTournaments < other.missingTournaments
                : houseNo > other.houseNo;
        }
    };
    // DEBUG(
    //     cerr << "applying cheat..." << endl;
    //     addTree(1, 1);
    // )
    priority_queue<HouseStats> houseStats;
    int totalParticipants = participantsTree[1];
    REP(x,n) {
        int tournaments = calcTournamentsLimit(x, n);
        if (tournaments < input[x]) {
            houseStats.push({x, input[x]-tournaments, totalParticipants});
        }
    }
    while (!houseStats.empty()) {
        HouseStats house = houseStats.top();
        houseStats.pop();
        if (house.totalParticipantsForCalculation == totalParticipants) {
            ++totalParticipants;
            addTree(house.houseNo, 1);
            DEBUG(
                cerr<<"missing "<<(house.missingTournaments)<<" for house [" << house.houseNo << "] - adding participant. Missing tournaments afterwards: " << endl;
                REP(x,n) {
                    cerr << input[x]-calcTournamentsLimit(x, n) << " ";
                }
                cerr << endl;
            )
        }
        
        int tournaments = calcTournamentsLimit(house.houseNo, n);
        if (tournaments < input[house.houseNo]) {
            house.totalParticipantsForCalculation = totalParticipants;
            house.missingTournaments = input[house.houseNo]-tournaments;
            houseStats.push(house);
        }
    }

    
    REP(x,n) {
        int tournaments = calcTournamentsLimit(x, n);
        if (tournaments == input[x]) {
            DEBUG(cerr<<"we cannot remove any participant - house "<<x<<" is already zeroed"<<endl;)
            return; // we can't remove anything if there is a house with 0 stat
        } else {
            houseStats.push({x, tournaments-input[x], totalParticipants});
        }
    }
    while(!houseStats.empty()) {
        HouseStats house = houseStats.top();
        houseStats.pop();
        DEBUG(cerr<<"trying to remove participant from house #"<<house.houseNo<<" (diff="<<house.missingTournaments<<")"<<endl;)
        addTree(house.houseNo, -1);

        bool possible=true;
        REP(x,n) {
            if (calcTournamentsLimit(x, n) < input[x]) {
                //cannot remove... - restore and finish algorithm
                DEBUG(cerr<<"...we cannot - too few tournaments for house "<<x<<" - "<<calcTournamentsLimit(x,n)<<" instead of "<<input[x]<<endl;)
                addTree(house.houseNo, 1);
                possible=false;
                break;
            }
        }
        if (!possible)
            continue;
        DEBUG(
            cerr<<"... yes we can. Missing tournaments afterwards: " << endl;
            REP(x,n) {
                cerr << input[x]-calcTournamentsLimit(x, n) << " ";
            }
            cerr << endl;
        )
        
        int tournaments = calcTournamentsLimit(house.houseNo, n);
        if (tournaments > input[house.houseNo]) {
            house.missingTournaments = tournaments - input[house.houseNo];
            houseStats.push(house);
        } else if (tournaments == input[house.houseNo]) {
            DEBUG(cerr<<"limit reached - current house is zeroed"<<endl;)
            return; // we can't remove anything else if there is a house with 0 stat
        }
    }
}

int solveCase() {
    int n;
    cin>>n;
    scores[0]={0,0};
    int realN = 0;
    int value;
    REP(x,n) {
        cin>>value;
        if (value) {
            input[realN++] = value;
        }
    }
    DEBUG(
        cerr << "input without empty houses:"<<endl;
        REP(x,realN)
            cerr << input[x] << " ";
        cerr << endl;
    )
    /*  minParticipants[0] = 2
        minParticipants[i] = 1 for 1 <= i <= realN-2
        minParticipants[realN-1] = 2

        sum(minPartipants, x..y) = y-x+1 (+1 if x=0) (+1 if y==realN-1)
    */
    treeHeaderSize=1;
    while(treeHeaderSize < realN)
        treeHeaderSize *= 2;
        
    REP(x,realN) {
        participantsTree[treeHeaderSize+x] = sumMinParticipants(x, x, realN);
    }
    buildTree(realN);
    DEBUG(
        cerr<<"initial tree (header size is " << treeHeaderSize << "): "<<endl;
        printTree(realN);
    )
    if (realN == 0) {
        return 2;// to satisfy stupid tests
    }
    
    DEBUG(REP(x,realN) {
        // scores[x].minLeft - min liczba graczy po lewej
        int maxParticipants = findNewton3ForResult(input[x]);
        participantsTree[treeHeaderSize+x] = sumMinParticipants(x, x, realN);
        int minLeft = sumMinParticipants(0, x-1, realN);
        int minRight = sumMinParticipants(x+1, realN-1, realN);
        int minHere = sumMinParticipants(x, x, realN);
        int leftTree = getTreeSum(0, x-1);
        int rightTree = getTreeSum(x+1, realN-1);
        int hereTree = getTreeSum(x, x);
        int minParticipants = minLeft*minHere*minRight + (minLeft+minRight)*newton2(minHere)+newton3(minHere);
        cerr<<"for "<<input[x]<<" found "<<maxParticipants<<" giving "<<newton3Tab[maxParticipants]<<"; "
            <<"for minParticipants we can play "<<minParticipants<<"/"<<input[x]<<" times; values="<<minLeft<<","<<minHere<<","<<minRight<<"; treeValues="<<leftTree<<","<<hereTree<<","<<rightTree<<endl;
    })
    //addParticipantsFromEdges(realN);
    addParticipantsFromBiggestDifference(realN);
    DEBUG(
        cerr<<"tree after all"<<endl;
        printTree(realN);
        cerr << "final tournaments possible"<<endl;
        REP(x,realN) {
            cerr << calcTournamentsLimit(x, realN) << " ";
        }
        cerr << endl << "diff: "<<endl;
        REP(x,realN) {
            cerr << calcTournamentsLimit(x, realN) - input[x] << " ";
        }
        cerr << endl;
    )
    return participantsTree[1];
}

void solve() {
    int t;
    cin >> t;
    REP(x,t) {
        cout << solveCase() << endl;
    }
}

#ifdef CALC_TIME
#include <ctime>
#endif

int main() {
    ios_base::sync_with_stdio(0);
#ifdef CALC_TIME
    clock_t begin = clock();
#endif
    solve();
#ifdef CALC_TIME
    cerr << "TIME: " << float(clock()-begin)/CLOCKS_PER_SEC << " s " << endl;
#endif
}