rt

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int f = 0, n = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') n = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        f = (f << 1) + (f << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f * n;
}
int T, n;
int p[1000005];
void solve() {
    n = read();
    for (int i = 1; i <= n; ++ i) p[i] = read(); 
    if (n == 1) cout << "0\n";
    else if (n == 2) cout << "1\n";
    else if (n == 3) cout << "2\n";
    else {
        int A = (p[1] & 1), flag = 0, cnt = 0;
        int k = n / 2 + (n & 1);
        for (int i = 2; i <= k; ++ i) {
            if ((p[i] & 1) != A) {
                flag = 1;
                break;
            }
        }
        int fl_a = 0, fl_b = 0, fl_c = 0, fl_d = 0;
        if (!flag) ++ cnt, fl_a = 1;
        if (p[1] == 1 || p[1] == n) ++ cnt, fl_b = 1;
        if ((p[1] == 1 && p[2] == n) || (p[1] == n && p[2] == 1) && !fl_a) ++ cnt, fl_c = 1;
        if (p[n] == n || p[n] == 1) ++ cnt, fl_d = 1;
        int maxn = p[1], minn = p[1];
        for (int i = 2; i < n; ++ i) {
            maxn = max(maxn, p[i]);
            minn = min(minn, p[i]);
            if (i == k && fl_a) continue;
            if (i == 2 && fl_c) continue;
            if (i == n - 1 && fl_d) continue;
            if (maxn == i || minn == n - i + 1) ++ cnt;
        }
        cout << cnt << '\n';
    }
}
signed main() {
    T = read();
    while (T --) {
        solve();
    }
    return 0;
}