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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define f first
#define s second
#define vec vector
#define pb push_back

using namespace std;

const int A = 1e6;

int n;
vec<ll> arr;

ll skip_size;

void get_skip(){
	int a = -1;
	int b = -1;

	foru(i, n) {
		ll left = i;
		ll right = n-1-i;
		if(left*right >= A) {
			a = i;
			break;
		}
	}

	for(int i = n-1; i>=0; i--) {
		ll left = i;
		ll right = n-1-i;
		if(left*right >= A) {
			b = i;
			break;
		}
	}

	if(a == -1) return;

	vec<ll> arr_ = {};
	swap(arr, arr_);

	for(int i = 0; i < n; i++){
		if(i == a){
			arr.pb(-1);
			i = b;
		}else{
			arr.pb(arr_[i]);
		}
	}

	skip_size = b-a+1;
}

ll triples(ll left, ll middle, ll right){
	ll out = 0;

	out += left*middle*right;
	out += left*middle*(middle-1)/2;
	out += right*middle*(middle-1)/2;
	out += middle*(middle-1)*(middle-2)/6;

	return out;
}

bool verify(int m){
	ll left = 0;
	ll right = n+m;

	foru(i, arr.size()){
		if(arr[i] == -1){
			right -= skip_size;
			left += skip_size;
			if(right < 0) return false;
		} else {
			right --;
			if(right < 0) return false;
			ll current = 1;
			while(triples(left, current, right) < arr[i]) {
				current++;
				right--;
				if(right < 0) return false;
			}
			left += current;
		}
	}
	return true;
}

void solve(){
	cin >> n;
	arr.resize(0);

	foru(_i, n) {
		int a; cin >> a;
		if(a == 0) continue;
		arr.pb(a);
	}

	n = arr.size();

	get_skip();

	int a = -1; //we know this one doesn't solve
	int b = 2e3; //we know this one does solve

	while(a+1 != b) {
		int m = (a+b)/2;
		if(verify(m)) b=m;
		else a=m;
	}

	cout << b+n << endl;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

	int t; cin >> t;
	foru(_i, t) solve();

    return 0;
}