#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

typedef long long LL;

int minimize(LL target, int L, int limit)
{
    int l = 0;
    int r = min(200, limit);

    while (l < r)
    {
        LL x = (l + r) / 2ll;

        LL val = x * (x - 1ll) * (x - 2ll) / 6ll;
        val += x * (x - 1ll) / 2ll * (L + limit - x);
        val += x * L * (limit - x);

        if (val >= target) r = (LL) x;
        else l = (LL) x + 1ll;
    }

    return l;
}

bool check(int n, const vector<int> &matches, int total)
{
    int L = 0;

    for (int i = 0; i < n; ++i)
    {
        int limit = total - L;
        int x = minimize(matches[i], L, limit);

        if (x == limit) return false;
        L += x;
    }

    return true;
}

inline int solve(int n, const vector<int> &matches)
{
    int l = 0;
    int r = 200 * n;

    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(n, matches, mid)) r = mid;
        else l = mid + 1;
    }

    return l;
}

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

    int t, n;
    cin >> t;

    while (t--)
    {
        cin >> n;
        vector<int> matches(n);
        for (int i = 0; i < n; i++) cin >> matches[i];
        cout << solve(n, matches) << "\n";
    }
}