#include<iostream>
#include<vector>
using namespace std;

int M = 1;

void update(vector<long long> &dp, int pos, long long val) {
    pos += M;

    dp[pos] = val;
    pos /= 2;

    while (pos > 0) {
        dp[pos] = dp[2 * pos] + dp[2 * pos + 1];
        pos /= 2;
    }
}

long long query(vector<long long> &dp, int a, int b) {
    a += M;
    b += M;

    long long res = dp[a];
    if (a != b) {
        res += dp[b];
    }

    while (a / 2 != b / 2) {
        if (a % 2 == 0) res += dp[a + 1];
        if (b % 2 == 1) res += dp[b - 1];
        a /= 2;
        b /= 2;
    }
    return res;
}

vector<vector<long long>> bc(1'000, vector<long long>(4));

long long calc(vector<long long> &dp, int pos, int players) {
    long long res = 0;
    
    // take exactly one playes from 'pos' position and other playes from left and right
    res += query(dp, 0, pos - 1) * players * query(dp, pos + 1, M - 1);

    // take exactly two playes form 'pos' position and other playes from left or right
    if (players >= 2) {
        res += query(dp, 0, pos - 1) * bc[players - 2][2];
        res += bc[players - 2][2] * query(dp, pos + 1, M - 1);
    }

    // take exactly tree playes form 'pos' position and no others
    if (players >= 3) {
        res += bc[players - 3][3];
    }

    return res;
}

int bin_search(vector<long long> &dp, int pos, int required) {
    int a = 1, b = 1000;
    while (a < b) {
        int players = (a + b) / 2;
        if (calc(dp, pos, players) < required) {
            a = players + 1;
        }
        else {
            b = players;
        }
    }
    return a;
}

bool is_fine(vector<long long> &dp, vector<long long> &v, int i) {
    long long elms = query(dp, i, i);
    long long cnt = calc(dp, i, elms);
    long long diff = cnt - v[i];
    return diff >= 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    bc[0] = {1, 1, 1, 1};
    bc[1] = {1, 2, 3, 4};
    for (int i = 2; i < bc.size(); i++) {
        bc[i][0] = bc[i - 1][0];
        bc[i][1] = bc[i][0] + bc[i - 1][1];
        bc[i][2] = bc[i][1] + bc[i - 1][2];
        bc[i][3] = bc[i][2] + bc[i - 1][3];
    }
    
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        n += 2;

        M = 1;
        while (M <= n) M *= 2;
        vector<long long> dp(2 * M);

        vector<long long> v(n);
        for (int i = 1; i < n - 1; i++) {
            cin >> v[i];
            if (v[i] > 0) {
                update(dp, i, 1);
            }
        }
        
        int a = 0, b = n - 1;
        while (v[a] == 0) a++;
        while (v[b] == 0) b--;
        update(dp, a, 2);
        update(dp, b, 2);

        while (true) {
            long long max_diff = 0;
            long long max_pos = 0;
            for (int i = a; i <= b; i++) {
                long long elms = query(dp, i, i);
                long long cnt = calc(dp, i, elms);
                long long diff = v[i] - cnt;
                if (max_diff < diff) {
                    max_diff = diff;
                    max_pos = i;
                }
            }

            if (max_diff == 0) {
                break;
            }
            update(dp, max_pos, query(dp, max_pos, max_pos) + 1);
        }

        while (true) {
            long long max_diff = 0;
            long long max_pos = 0;
            for (int i = a; i <= b; i++) {
                long long elms = query(dp, i, i);
                long long cnt = calc(dp, i, elms);
                long long diff = cnt - v[i];
                if (max_diff < diff) {
                    max_diff = diff;
                    max_pos = i;
                }
            }

            if (max_diff > 0) {
                long long mx_val = query(dp, max_pos, max_pos);
                update(dp, max_pos, mx_val - 1);
                bool fine = true;
                for (int i = a; i <= b; i++) {
                    long long elms = query(dp, i, i);
                    long long cnt = calc(dp, i, elms);
                    if (v[i] - cnt > 0) {
                        fine = false;
                        break;
                    }
                }    
                if (! fine) {
                    update(dp, max_pos, mx_val);
                    break;
                }
            }
            else {
                break;
            }
        }

        // test if left border can be decreased
        long long aval = query(dp, a, a);
        update(dp, a, aval - 1);
        
        bool afine = true;
        for (int q = a; q <= b; q++) {
            long long elms = query(dp, q, q);
            long long cnt = calc(dp, q, elms);
            if (v[q] - cnt > 0) {
                afine = false;
                break;
            }
        }
        if (! afine) {
            update(dp, a, aval);
        }     

        // test if right border can be decreased
        long long bval = query(dp, b, b);
        update(dp, b, bval - 1);
        
        bool bfine = true;
        for (int q = a; q <= b; q++) {
            long long elms = query(dp, q, q);
            long long cnt = calc(dp, q, elms);
            if (v[q] - cnt > 0) {
                bfine = false;
                break;
            }
        }
        if (! bfine) {
            update(dp, b, bval);
        }     

        bool can_be_better = false;
        for (int i = a + 1; i <= b - 1; i++) {
            if (query(dp, i, i) > 1) {
                can_be_better = true;
                break;
            }
        }
        
        if (can_be_better) {
            for (int i = a; i <= b; i++) {
                for (int j = a; j <= b; j++) {
                    if (i == j) continue;
                    long long ival = query(dp, i, i);
                    long long jval = query(dp, j, j);
                    update(dp, i, ival - 2);
                    update(dp, j, jval + 1);

                    bool fine = true;
                    if (is_fine(dp, v, i) && is_fine(dp, v, j)) {
                        for (int q = a; q <= b; q++) {
                            long long elms = query(dp, q, q);
                            long long cnt = calc(dp, q, elms);
                            if (v[q] - cnt > 0) {
                                fine = false;
                                break;
                            }
                        }        
                    }
                    else {
                        fine = false;
                    }
                    if (fine) {
                        int yyy = 1;
                    }
                    else {
                        update(dp, i, ival);
                        update(dp, j, jval);
                    }
                }
            }
        }

        long long res = 0;
        for (int i = M; i < dp.size(); i++) {
            res += dp[i];
            //cerr << dp[i] << ' ';
        }
        //cerr << endl;
        
        cout << res << endl;
    }

    return 0;
}