1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);
 
// #define int ll
typedef long long ll;

using namespace std;
template <typename T> struct tag:reference_wrapper <T>{ using reference_wrapper <T>::reference_wrapper; };
template <typename T1, typename T2> static inline tag <ostream> operator<<(tag <ostream> os, pair<T1, T2> const& p){ return os.get()<<"{"<<p.first<<", "<<p.second<<"}", os;}
template <typename Other> static inline tag <ostream> operator<<(tag <ostream> os, Other const& o){ os.get()<<o; return os; }
template <typename T> static inline tag <ostream> operator <<(tag <ostream> os, vector <T> const& v){ os.get()<<"["; for (int i=0; i<v.size(); i++) if (i!=v.size()-1) os.get()<<v[i]<<", "; else os.get()<<v[i]; return os.get()<<"]", os; }
template <typename T> static inline tag <ostream> operator <<(tag <ostream> os, set <T> const& s){ vector <T> v; for (auto i: s) v.push_back(i); os.get()<<"["; for (int i=0; i<v.size(); i++) if (i!=v.size()-1) os.get()<<v[i]<<", "; else os.get()<<v[i]; return os.get()<<"]", os; }

int n;
vector<int> dp;

/*
x, (y + 1)
a * x * (y + 1) + x * (x - 1) * (a + y + 1)/2 + x * (x - 1)* (x - 2)
axy + ax + (axx + xxy - ax -xy + xx - x)/2 + (xxx -3xx +2x)/6


6ax - 3ax -3xy
6ay + 3ax + 3xy


(x + 1), y
a * (x + 1) * y + (x + 1) * x * (a + y)/2 + (x + 1) * x * (x - 1)/6
axy + ay + (axx + xxy + ax + xy)/2 + (xxx - x)/6
*/

long long games(long long a, long long b, long long c){
    long long ans = a * b * c;
    ans += (b * (b - 1) / 2) * (a + c);
    ans += (b * (b - 1) * (b - 2) / 6);
    return ans;
}

int bs(int mini, int pref, int suf){
    int ans = 0;
    if(suf < 200 && games(pref, suf, 0) < mini){
        return suf;
    }
    int po = -1, ko = min(200, suf), sr;
    while(po + 1 < ko){
        sr = (po + ko) / 2;
        if(games(pref, sr, suf - sr) >= mini){
            ko = sr;
        } else {
            po = sr;
        }
    }
    return ko;
}

bool check(int k, vector<int> &ai){
    dp.assign(n + 2, 0);
    int pref = 0;
    int suf = k;
    int people;
    for(int i = 1; i <= n; i++){
        people = bs(ai[i], pref, suf);
        if(games(pref, people, suf - people) < ai[i]){
            return false;
        }
        dp[i] = people;
        suf -= people;
        pref += people;
    }
    return true;
}

void solve(){
    cin >> n;
    vector<int> ai(n + 2, 0);
    for(int i = 1; i <= n; i++){
        cin >> ai[i];
    }

    int po = 0, ko = 200 * n, sr;
    while(po + 1 < ko){
        sr = (po + ko)/2;
        if(check(sr, ai)){
            ko = sr;
        } else {
            po = sr;
        }
    }
    cout << ko << "\n";
}

int32_t main(){
    BOOST;
    
    int q; cin >> q;
    while(q--){
        solve();
    }
    return 0;
}