#include <algorithm>
#include <cstdio>

constexpr int MAXN = 100000 + 2;

int a[MAXN], tmp[MAXN], p[MAXN], rnk[MAXN];

std::pair<int, int> stk[MAXN];

bool merge(
  std::pair<int, int>& pr1,
  std::pair<int, int> pr2
) {
    if (pr1.second + 1 == pr2.first) {
        return pr1.second = pr2.second, true;
    }
    if (pr2.second + 1 == pr1.first) {
        return pr1.first = pr2.first, true;
    }
    return false;
}

bool valid(int n) {
    int top = 0;

    for (int i = 1; i <= n; i ++) {
        stk[++ top] = {p[i], p[i]};

        while (top > 1 && merge(stk[top - 1], stk[top])) {
            top --;
        }
    }

    return top == 1;
}

void resort(int l, int r) {
    for (int i = l; i <= r; i ++) {
        tmp[i] = a[i];
    }
    std::sort(tmp + l, tmp + r + 1);

    for (int i = l; i <= r; i ++) {
        rnk[tmp[i]] = i - l + 1;
    }

    for (int i = l; i <= r; i ++) {
        p[i - l + 1] = rnk[a[i]];
    }
}

void bucketResort(int l, int r, int V) {
    for (int i = 1; i <= V; i ++) {
        tmp[i] = 0;
    }
    for (int i = l; i <= r; i ++) {
        tmp[rnk[a[i]]] = i - l + 1;
    }

    for (int i = 1, rank = 0; i <= V; i ++) {
        if (tmp[i]) {
            p[tmp[i]] = ++ rank;
        }
    }
}

void solve() {
    int n, ans = 0;
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
    }

    for (int l = 1; l <= n; ans ++) {
        int len = 1;
        while (l + len - 1 <= n &&
          (resort(l, l + len - 1), valid(len))) {
            len <<= 1;
        }

        int L = l + (len >> 1) - 1;
        int R = std::min(l + len - 2, n);

        resort(l, R);

        while (L < R) {
            int r = (L + R + 1) >> 1;

            if (bucketResort(l, r, R - l + 1),
              valid(r - l + 1)) {
                L = r;
            } else {
                R = r - 1;
            }
        }

        l = L + 1;
    }

    printf("%d\n", n - ans);
}

int main() {
    int T;
    scanf("%d", &T);

    while (T --) {
        solve();
    }

    return 0;
}