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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include "bits/stdc++.h"
using namespace std;

#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define per(i, b, e) for (int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e)-1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto& operator<<(auto& o, pair<auto, auto> p) {
  return o << "(" << p.st << ", " << p.nd << ")";
}
auto operator<<(auto& o, auto x) -> decltype(end(x), o) {
  o << "{";
  int i = 0;
  for (auto e : x)
    o << ", " + 2 * !i++ << e;
  return o << "}";
}
#ifdef LOCAL
#define deb(x...)                       \
  cerr << "[" #x "]: ", [](auto... $) { \
    ((cerr << $ << "; "), ...) << endl; \
  }(x)
#else
#define deb(...)
#endif

const int N = 200;
ll newton[N][4];

bool check(vi& a, int k) {
  // cout << "Sprawdzam dla " << k << "\n";
  int n = SZ(a);

  ll prev = 0;
  for (int i = 0; i < n; i++) {
    if (!a[i]) {
      continue;
    }

    bool udalo_sie = false;
    for (ll j = 1; j <= min(N - 1, k); j++) {
      ll cur =
          newton[j][3] + newton[j][2] * (prev + (k - j)) + j * prev * (k - j);
      // cout << "Gdybym " << i << "-temu dal " << j << " to by mial " << cur
      //      << "\n";
      if (cur >= a[i]) {
        // cout << "Moge dac " << i << "-temu " << j << "\n";
        k -= (int)j;
        prev += j;
        udalo_sie = true;
        break;
      }
    }
    if (!udalo_sie)
      return false;
  }
  return true;
}

void solve() {
  int n;
  cin >> n;
  vi a(n);

  int lo = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i])
      lo++;
  }

  int hi = n * 201;

  while (lo < hi - 1) {
    int mid = (lo + hi) / 2;
    if (check(a, mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }

  cout << hi << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie();

  newton[0][0] = 1;
  for (int i = 1; i < N; i++) {
    // cout << i << ": ";
    newton[i][0] = 1;
    for (int k = 1; k <= 3; k++) {
      newton[i][k] = newton[i - 1][k] + newton[i - 1][k - 1];
      // cout << newton[i][k] << " ";
    }
    // cout << "\n";
  }

  int t;
  cin >> t;
  while (t--)
    solve();
}