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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
ll T[LIM], n;
ll calc(ll a, ll b, ll c) {
	return a*b*c + b*(b-1)/2 * (a+c) + b*(b-1)*(b-2)/6;
}
bool check(ll x) {
	ll y=0;
	rep(i, n) {
		if(!T[i]) continue;
		ll po=0, ko=x-y;
		if(x-y==0) return false;
		if(calc(y, 1, x-y-1)>=T[i]) {
			++y;
			continue;
		}
		while(po<ko) {
			ll sr=(po+ko)/2;
			if(calc(y, sr, x-y-sr)<T[i]) po=sr+1; else ko=sr;
		}
		if(calc(y, po, x-y-po)<T[i]) return false;
		y+=po;
	}
	return true;
}
void solve() {
	cin >> n;
	rep(i, n) cin >> T[i];
	ll po=0, ko=n+2000;
	while(po<ko) {
		ll sr=(po+ko)/2;
		if(check(sr)) ko=sr; else po=sr+1;
	}
	cout << po << '\n';
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int _=1;
	cin >> _;
	while(_--) solve();
}