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
#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> ai;


int czy_wystarczy(int zaw) {
	int lewo = 0;
	for(int i = 0; i < n; i++) {
		long long akt = 0;
		while( lewo * akt * (zaw-akt-lewo) + (zaw-akt)*akt*(akt-1)/2  + akt*(akt-1)*(akt-2)/6 < ai[i] ) {
			akt++;
			if(lewo+akt > zaw)
				return 0;
		}
		lewo += akt;
	}
	return 1;
}



void do_test_case() {
	cin >> n;
	ai.clear();
	ai.resize(n);
	
	for(int i = 0; i <n; i++)
		cin >> ai[i];
	
	
	int wynik_min = 1, wynik_max = 2300000;
	while(wynik_min < wynik_max) {
		int mid = (wynik_max + wynik_min) /2;
		if( !czy_wystarczy(mid) ) {
			wynik_min = mid+1;
		} else {
			wynik_max = mid;
		}
	}
	cout <<  wynik_min << endl;
	
}


int main() {
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		do_test_case();
    return 0;
}