#include <bits/stdc++.h>
using namespace std;

#define all(a) begin(a), end(a)
using ll = long long;

constexpr int LIMIT = 2001; // max_ans <= 2 * sqrt(A)
// constexpr int LIMIT = 10;

int get(vector<int> const &a, int pos) {
    assert(pos >= 0);
    if (pos >= a.size())
        return a.back();
    return a[pos];
}

int get(array<int, LIMIT> const &a, int pos) {
    assert(pos >= 0);
    if (pos >= a.size())
        return a.back();
    return a[pos];
}

ll C3(ll x) { return x * (x - 1) * (x - 2) / 6; }
ll C2(ll x) { return x * (x - 1) / 2; }

// int go_down(int l, int r, int x, int needed) {
//     while (C3(x) + (l + r) * C2(x) + l * r * (ll)x >= needed)
//         --x;
//     return x + 1;
// }

ll get(int l, int r, int x) { return C3(x) + (l + r) * C2(x) + (ll)x * l * r; }

// If we have i + x players to the left, how many players should be on [i, n) (without needed -(n-i))
vector<int> brute(vector<int> const &a) {
    int n = a.size();

    vector<int> prev{0};
    for (int pos = n - 1; pos >= 0; --pos) {
        vector<int> result(LIMIT, 1e9);
        for (int left = 0; left < LIMIT; left++) {
            for (int x = 0; x < LIMIT; x++) {
                int right = get(prev, left + x);
                if (get(left + pos, right + (n - 1 - pos), x + 1) >= a[pos])
                    result[left] = min(result[left], x + right);
            }
        }

        prev = result;
    }

    return prev;
}

vector<int> solve_slow(vector<int> const &a) {
    int n = a.size();

    vector<int> prev{0};
    for (int pos = n - 1; pos >= 0; --pos) {
        // int best = 1e9;
        vector<int> result;
        for (int left = 0; left < LIMIT; left++) {
            int cur = 1e9;

            for (int x = 0; true; x++) {
                int right = get(prev, left + x);
                bool good = get(left + pos, right + (n - 1 - pos), x + 1) >= a[pos];
                // cerr << pos << " - " << left << " " << x << " -> " << right << " ? " << good << "\n";
                if (good) {
                    cur = min(cur, x + right);

                    // We will not make right less, so we can stop increasing x
                    if (left + x >= prev.size())
                        break;
                }
            }

            // cerr << "best: " << pos << " -> " << best << " - " << left << " " << cur << "\n";
            // if (left + cur > best)
            //     break;

            result.push_back(cur);
            // best = left + cur;
        }

        // cerr << "result: " << pos << " -> ";
        // for (auto i : result)
        //     cerr << i << " ";
        // cerr << "\n";

        prev = std::move(result);
    }

    return prev;
}

int solve(vector<int> const &a) {
    int n = a.size();

    array<int, LIMIT> prev;
    fill(all(prev), 0);

    for (int pos = n - 1; pos >= 0; --pos) {
        int prev_x = LIMIT;
        array<int, LIMIT> result;
        for (int left = 0; left < LIMIT; left++) {
            auto test_x = [&](int x) {
                int right = get(prev, left + x);
                return get(left + pos, right + (n - 1 - pos), x + 1) >= a[pos];
            };

            int x = prev_x;
            while (x >= 0 && test_x(x))
                --x;

            while (x < 0 || !test_x(x))
                ++x;

            int right = get(prev, left + x);

            int cur = x + right;
            result[left] = cur;

            prev_x = x;
        }

        // cerr << "result: " << pos << " -> ";
        // for (auto i : result)
        //     cerr << i << " ";
        // cerr << "\n";

        for (int i = 1; i < result.size(); i++)
            assert(result[i] >= result[i - 1] - 1);

        prev = std::move(result);
    }

    return prev[0];
}

vector<int> random_sample() {
    // int n = 1 + rand() % (int)2e5;
    int n = 1 + rand() % 100;
    vector<int> a(n);
    for (auto &i : a)
        i = rand() % ((int)1e6 + 1);
    return a;
}

void test() {
    auto a = random_sample();
    a.erase(remove(all(a), 0), end(a));

    int x = brute(a)[0], y = solve(a); // Tricky, because x is not a brute baseline
    // int y = solve(a), x = y;

    if (x == y) {
        cerr << "OK" << endl;
        return;
    }

    for (auto i : a)
        cerr << i << " ";
    cerr << "\n";

    cerr << x << " " << y << "\n";
    exit(1);
}

void solve() {
    // while (1)
    //     test();

    int n;
    cin >> n;

    vector<int> a(n);
    for (auto &i : a)
        cin >> i;

    a.erase(remove(all(a), 0), end(a));
    n = a.size();

    cout << solve(a) + n << "\n";
}

int main() {
    // srand(time(nullptr));

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int tests = 1;
    cin >> tests;

    while (tests--)
        solve();
}