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
#include <bits/stdc++.h>
#define e using u=ostream;template<class a,class b>u&operator<<(u&o,pair<a,b>&x)
using namespace std;e;u&operator<<(u&o,string&s){return o<<s.c_str();}template<
class t>auto operator<<(u&o,t&x)->decltype(x.end(),o){o<<'{';int i=2;for(auto y:
x)o<<", "+i<<y,i=0;return o<<'}';}e{return o<<'('<<x.first<<", "<<x.second<<')';}
#ifdef DEBUG
#define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define LOG(...)
#endif
#define ff first
#define ss second
#define ll long long

const ll maxtotal = 1000000;
const ll maxdom = 10000;

vector <ll> po2(maxdom);
vector <ll> po3(maxdom);

int n;

void init() {
	po2[0] = 0;
	for (ll i = 1; i < maxdom; i++) {
		po2[i] = i*(i-1)/2;
	}
	po3[0] = 0;
	po3[1] = 0;
	for (ll i = 2; i < maxdom; i++) {
		po3[i] = i*(i-1)*(i-2)/6;
	}
}

ll count(ll p, ll s, ll x) {
//	LOG(p, s, x, po3[x], max(0LL, po2[x] * (p-x)));
	return po3[x] + max(0LL, po2[x] * (p-x)) + max(0LL, x*s*(p-s-x));
}


bool check(vector <ll>& v, ll p) {
	ll s = 0;
	
	for (int i = 0; i < n; i++) {
		LOG(i);
		ll l = 0;
		ll r = min(maxdom-1, p-s+1);
		ll x;
		while (l < r) {
			x = (l+r) / 2;
			//LOG(count(p, s, x), p, s, x, v[i]);
			if (count(p, s, x) >= v[i]) {
				r = x;
//				LOG(count(p, s, x), x, v[i], r, l);
			}
			else
				l = x+1;
		}
		LOG(l);
		s += l;
		if (s > p)	
			return false;
	}
	return true;
}


ll solve() {
	cin >> n;
	vector <ll> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	ll l = 0;
	ll r = maxtotal;
	ll p;
	while (l < r) {
		p = (l+r) / 2;
		LOG(p);
		if (check(v, p))
			r = p;
		else
			l = p+1;
	}
	return l;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	init();
	int t;
	cin >> t;
	while (t--) {
		cout << solve() << "\n";
	}

}