ARC 181

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        int N;
        cin >> N;
        vint P(N);
        rep(i, N) {
            cin >> P[i];
            P[i]--;
        }

        vint v(N);
        iota(all(v), 0);

        if (v == P) {
            cout << 0 << endl;
            return;
        }

        int mx = -1;
        rep(i, N) {
            if (i == P[i] && mx < P[i]) {
                cout << 1 << endl;
                return;
            }
            chmax(mx, P[i]);
        }
        if (P.front() == N - 1 && P.back() == 0)
            cout << 3 << endl;
        else
            cout << 2 << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}