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
import sys

def find_min_s(sum_a):
    low = 3
    high = 2 * 10**6
    while low < high:
        mid = (low + high) // 2
        if mid * (mid - 1) * (mid - 2) // 6 >= sum_a:
            high = mid
        else:
            low = mid + 1
    if low * (low -1)*(low-2)//6 < sum_a:
        return low +1
    return low

def solve():
    input = sys.stdin.read().split()
    idx = 0
    t = int(input[idx])
    idx +=1
    for _ in range(t):
        n = int(input[idx])
        idx +=1
        a = list(map(int, input[idx:idx+n]))
        idx +=n
        sum_a = sum(a)
        if sum_a ==0:
            print(0)
            continue
        
        s_sum = find_min_s(sum_a)
        print(s_sum)

if __name__ == "__main__":
    solve()