#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef LOCAL
#include "../debug/debug.h"
#else
#define debug(...)
#define debugArr(...)
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = long double;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vvl = vector<vl>;

#define mp make_pair
#define eb emplace_back
#define pb push_back
#define x first
#define y second
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend() 
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define ft front()
#define bk back()
#define rsz resize
#define ins insert
#define each(a,x) for(auto&a:x)

template<class T> bool ckmin(T& a, T b) { return b<a?a=b,1:0; }
template<class T> bool ckmax(T& a, T b) { return b>a?a=b,1:0; }
template<class T> int lwb(vector<T>& a, const T& b) { return int(lower_bound(all(a),b)-bg(a)); }
template<class T> int upb(vector<T>& a, const T& b) { return int(upper_bound(all(a),b)-bg(a)); }
template<class T> void remdup(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }

constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bitlog(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
constexpr int pct(ll x) { return __builtin_popcountll(x); }
constexpr int bitlog(ll x) { return x == 0 ? 0 : 63 - __builtin_clzll(x); }

constexpr ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }  // divide a by b rounded up
// constexpr ll cdiv(ll a, ll b) { return (a + b - 1) / b; }
constexpr ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }  // divide a by b rounded down
constexpr int cdiv(int a, int b) { return a / b + ((a ^ b) > 0 && a % b); }  // divide a by b rounded down
constexpr int fdiv(int a, int b) { return a / b - ((a ^ b) < 0 && a % b); }  // divide a by b rounded down

const pi MOVES[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

#ifdef LOCAL
mt19937_64 rng(0xabadbeef);
#else
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

ll randr(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }

const int N = 5000;
ll b2[N];
ll b3[N];

void init() {
    rep(i,1,N) {
        b2[i] = 1LL * i * (i - 1);
        b2[i] /= 2;
    }
    rep(i,2,N) {
        b3[i] = b2[i] * (i - 2);
        b3[i] /= 3;
    }
}

ll f(ll l, int c, ll r) {
    ll res = l * c * r + b2[c] * (l + r) + b3[c];
    return res;    
}

const ll INF = 1e6+1;

/**
 * XDDDDD ALE JESTEM GŁUPI
 * ZOSTAWIAM DLA PRZESTROGI ŻEBY SIĘ NA JEDNYM SOLVIE NIE SKUPIAĆ
 */
// ll get_needed_z_prawej(ll l, int c, ll target) {
//     ll num = target - b3[c] - b2[c] * l;
//     if (num <= 0) return 0;
//     ll den = b2[c] + l * c;
//     return cdiv(num, den); 
//     // return cdiv(target - b3[c] - b2[c] * l, b2[c] + l * c);
// }

// void solve() {
//     int n;
//     cin >> n;
//     vl a;
    
//     rep(i,0,n) {
//         int x;
//         cin >> x;
//         if (x != 0) a.eb(x);
//     }

//     n = sz(a);

//     vl dp[2]; // dp[i][j] -> ile potrzeba dodać z prawej minimalnie, żeby wyszło z lewej j

//     dp[0].reserve(3000);
//     dp[1].reserve(3000);

//     dp[1] = {0};
//     dp[0] = {INF};

//     rep(i,0,n) {
//         int nxt = i & 1;
//         int prv = nxt ^ 1;

//         ll z_lewej_min = i;
//         ll z_prawej_min = n - i - 1;
        
//         fill(all(dp[nxt]), INF);

//         for (int j_plus_k = 1; dp[nxt].bk > 0; j_plus_k++) {
//             if (sz(dp[nxt]) <= j_plus_k) {
//                 dp[nxt].eb(INF);
//             }

//             auto calc = [&](ll x) {
//                 int j = x;
//                 int k = j_plus_k - x;
//                 ll z_prawej = get_needed_z_prawej(z_lewej_min + j, k + 1, a[i]) - z_prawej_min;
//                 ckmax(z_prawej, dp[prv][j] - k);
//                 ckmax(z_prawej, 0LL);
//                 return z_prawej;
//             };

//             if (i == 0) {
//                 dp[nxt][j_plus_k] = calc(0);
//                 continue;
//             }

//             int l = 1;
//             int r = min(sz(dp[prv]) - 1, j_plus_k);
            
//             while (r - l > 6) {
//                 int nl = l + (r - l) / 3;
//                 int nr = r - (r - l) / 3;
//                 ll fl = calc(nl);
//                 ll fr = calc(nr);
//                 ckmin(dp[nxt][j_plus_k], fl);
//                 ckmin(dp[nxt][j_plus_k], fr);

//                 if (fl < fr) {
//                     r = nr - 1;
//                 }
//                 else {
//                     l = nl + 1;
//                 }
//             }

//             while (l <= r) {
//                 ckmin(dp[nxt][j_plus_k], calc(l++));
//             }
//         }
//     }

//     int idx = (n - 1) & 1;

//     per(i,0,sz(dp[idx])) {
//         if (dp[idx][i] == 0) {
//             cout << i + n << '\n';
//             return;
//         }
//     }

// }

void solve() {
    int n;
    cin >> n;
    vl a;
    
    rep(i,0,n) {
        int x;
        cin >> x;
        if (x != 0) a.eb(x);
    }

    n = sz(a);

    auto calc = [&](ll on_right) {
        ll on_left = 0;
        rep(i,0,n) {
            ll got = 0;
            while (f(on_left, got, on_right) < a[i]) {
                if (on_right == 0) return false;
                got++;
                on_right--;
            }
            on_left += got;
        }
        return true;
    };

    ll res = INF;
    ll l = n;
    ll r = INF;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (calc(mid)) {
            res = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }

    cout << res << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    init();

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

    return 0;
}