Stripe, Token and Two Players

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct SegTree {
    int n;
    vector<int> mx;

    void init(int n_) {
        n = n_;
        mx.assign(4 * n + 4, 0);
    }

    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            mx[v] = val;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm) update(v << 1, tl, tm, pos, val);
        else update(v << 1 | 1, tm + 1, tr, pos, val);
        mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    }

    void update(int pos, int val) {
        update(1, 1, n, pos, val);
    }

    int findFirst(int v, int tl, int tr, int l, int r, ll need) {
        if (r < tl || tr < l || mx[v] <= need) return -1;
        if (tl == tr) return tl;
        int tm = (tl + tr) >> 1;
        int res = findFirst(v << 1, tl, tm, l, r, need);
        if (res != -1) return res;
        return findFirst(v << 1 | 1, tm + 1, tr, l, r, need);
    }

    int findFirst(int l, int r, ll need) {
        if (l > r) return -1;
        return findFirst(1, 1, n, l, r, need);
    }
};

struct Solver {
    int n;
    vector<ll> a;
    vector<vector<pair<int, int>>> events;
    vector<int> cnt, endAt;
    set<int> bad; // bad powers, with sentinels 0 and n+1
    SegTree seg;

    void putInterval(int l, int r) {
        if (l > r) return;
        endAt[l] = r;
        seg.update(l, r - l + 1);
    }

    void eraseIntervalStart(int l) {
        endAt[l] = 0;
        seg.update(l, 0);
    }

    void makeBad(int p) {
        if (++cnt[p] != 1) return;

        auto itR = bad.upper_bound(p);
        int rb = *itR;
        int lb = *prev(itR);

        int l = lb + 1, r = rb - 1;
        eraseIntervalStart(l);
        putInterval(l, p - 1);
        putInterval(p + 1, r);

        bad.insert(p);
    }

    void makeGood(int p) {
        if (--cnt[p] != 0) return;

        auto it = bad.find(p);
        int lb = *prev(it);
        int rb = *next(it);

        if (lb + 1 <= p - 1) eraseIntervalStart(lb + 1);
        if (p + 1 <= rb - 1) eraseIntervalStart(p + 1);

        bad.erase(it);
        putInterval(lb + 1, rb - 1);
    }

    int run() {
        cin >> n;
        a.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) cin >> a[i];

        events.assign(n + 1, {});
        cnt.assign(n + 2, 0);
        endAt.assign(n + 2, 0);
        bad.clear();
        bad.insert(0);
        bad.insert(n + 1);

        seg.init(n);
        putInterval(1, n); // initially all powers are good

        bool startLosing = false;

        for (int i = n; i >= 1; i--) {
            for (auto [p, delta] : events[i]) {
                if (delta == 1) makeBad(p);
                else makeGood(p);
            }

            ll A = a[i];
            ll Rll = (ll)n - i - A; // p must be <= Rll to not finish immediately

            if (i == 1) {
                // Initial power is exactly 1. It is losing iff [1, 1+A] is good
                // and finishing immediately is impossible.
                if (Rll >= 1 && endAt[1] != 0 && (ll)endAt[1] >= A + 1) {
                    startLosing = true;
                }
                break;
            }

            if (Rll < 1) continue;
            int R = (int)Rll;

            int pos = 1;
            while (pos <= R) {
                int l = seg.findFirst(pos, R, A);
                if (l == -1) break;

                int r = endAt[l];
                int u = (int)min<ll>((ll)r - A, R);

                // States (i, p), p in [l, u], are losing.
                for (int p = l; p <= u; p++) {
                    events[i - 1].push_back({p, 1});
                    int rem = i - p - 1;
                    if (rem >= 1) events[rem].push_back({p, -1});
                }

                pos = l + 1;
            }
        }

        return startLosing ? 2 : 1;
    }
};

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        Solver solver;
        cout << solver.run() << '\n';
    }

    return 0;
}