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
def ile_min(a):
	n = int((a*6)**(1/3))
	while  n*(n-1)*(n-2)//6<a:
		n+=1
	return n

def c2(n):
	return n*(n-1)//2	
def c3(n):
	return n*(n-1)*(n-2)//6
	
def solve(n,a):
	r = ile_min(sum(a))
	p = 0
	while a[p]==0: p+=1
	k = n-1
	while a[k]==0: k-=1
	s = 0
	#print(p,k)
	if p==k:
		return r
	while p<k:
		if a[p]==0:
			p+=1
			continue
		pn = 1
		while s+pn<r and s*pn*(r-s-pn)+c2(pn)*(r-s-pn)+c2(pn)*s+c3(pn)<a[p]: pn+=1
		if s+pn==r:
			r+=1
		#print("p=",p,"pn=",pn)
		s+=pn
		p+=1
	kn = r-s
	while c2(kn)*s<a[k]:
		r+= 1
		kn = r-s
	return r
	
for _ in range(int(input())):
	n = int(input())
	a = list(map(int,input().split()))
	print(solve(n,a))