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
#include <bits/stdc++.h>
using namespace std;
const int MX=200200;
int t,n,a[MX];
long long C3(long long x) {
  long long y=x-1,z=x-2;
  if (x&1) y/=2; else x/=2;
  if (x%3==0) x/=3; else if (y%3==0) y/=3; else z/=3;
  return (x*y*z);
}
long long C2(long long x) {
  long long y=x-1;
  if (x&1) y/=2; else x/=2;
  return (x*y);
}
bool check(int x) {
  int was=0;
  for (int i=1; i<n; i++) {
    int le=0,ri=3*a[i];
    while (le<ri) {
      long long mid=(le+ri)/2;
      long long rgh=max(0LL,x-mid-was);
      long long cur=C3(mid)+C2(mid)*(was+rgh)+was*rgh*mid;
      if (cur>=a[i]) ri=mid; else le=mid+1;
    }
    if ((was+=ri)>x) return false;
  }
  long long cur=C3(x-was)+C2(x-was)*was;
  return (cur>=a[n]);   
}
int main() {
  scanf("%d",&t);
  while (t--) {
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]);
    int le=3,ri=5000000;
    while (le<ri) {
      int mid=(le+ri)/2;
      if (check(mid)) ri=mid; else le=mid+1;
    }
    printf("%d\n",ri);
  }
  return 0;
}