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
#include <bits/stdc++.h>

#define ndl '\n'
#define ll long long
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define all(x) (x).begin(), (x).end()

using namespace std;

ll trojmian(ll n) {
    if(n < 3) return 0;
    return n * (n-1) * (n-2) / 6;
}

ll dwumian(ll n) {
    if(n < 2) return 0;
    return n * (n-1) / 2;
}

void rob() {
    ll n; cin>>n;
    ll sum = 0;
    vector<ll> t;
    for(ll i=0;i<n;i++) {
        ll tmp; cin>>tmp;
        if(tmp != 0) {
            t.push_back(tmp);
        }
        sum+=tmp;
    }

    n = t.size();

    if(n == 0) {
        cout<<0<<'\n';
        return;
    }

    auto sprawdzajka = [&](ll x) {
        ll used = 0;

        for(ll i=0;i<t.size();i++) {
            if(x - used <= 0) {
                return false;
            }
            ll a = 0, b = x - used + 1;
            while(a + 1 < b) {
                ll sr = (a+b)/2;
                if(sr * used * (x - used - sr) + dwumian(sr) * (x - sr) + trojmian(sr) < t[i]) {
                    a = sr;
                } else {
                    b = sr;
                }
            }
            if(b * used * (x - used - b) + dwumian(b) * (x - b) + trojmian(b) >= t[i]) {
                used += b;
            } else {
                return false;
            }
        }
        return true;
    };

    ll a = 2, b = 10000000;
    while(a+1<b) {
        ll sr = (a+b)/2;
        if(sprawdzajka(sr)) {
            b = sr;
        } else {
            a = sr;
        }
    }
    cout<<b<<'\n';
    return;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll t;
    cin>>t;
    for(ll i=0;i<t;i++)
        rob();
}