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

const int N = 5e5 + 10;
int a[N], pos[N];

void solve()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    int cnt = 0;

    auto dfs = [&](auto self, int l, int r) {
        if(l >= r)  return;
        int mid = (l + r + 1) / 2, midVal = a[mid];
        // printf("::%d %d %d %d\n", l, r, mid, midVal);
        vector<int> lp, rp;
        if(midVal < mid) {
            for(int i = l; i <= midVal; i++)    if(a[i] >= midVal && i != a[i])    lp.push_back(i);
            for(int v = l; v <= midVal; v++)    if(pos[v] >= midVal && pos[v] != v)     rp.push_back(pos[v]);
            sort(rp.begin(), rp.end(), greater<int>());
        } else if(midVal >= mid) {
            for(int v = midVal; v <= r; v++)    if(pos[v] <= midVal && pos[v] != v) lp.push_back(pos[v]);
            for(int i = midVal; i <= r; i++)    if(a[i] <= midVal && i != a[i])   rp.push_back(i);
            sort(lp.begin(), lp.end());
        }
        // assert(lp.size() == rp.size());
        // if(lp.size() != rp.size()) {
        //     printf("___\n");
        //     for(int i = 1; i <= n; i++) printf("%d ", a[i]);
        //     printf("\n");
        //     for(int p: lp)  printf("%d ", p);
        //     printf("\n");
        //     for(int p: rp)  printf("%d ", p);
        //     printf("\n");
        // }

        for(int i = 0; i < lp.size(); i++) {
            int p1 = lp[i], p2 = rp[i];
            if(p1 == p2)    continue;
            // printf("::::%d %d %d %d\n", p1, a[p1], p2, a[p2]);
            swap(a[p1], a[p2]);
            swap(pos[a[p1]], pos[a[p2]]);
            cnt++;
        }

            // printf("___\n");
            // for(int i = 1; i <= n; i++) printf("%d ", a[i]);
            // printf("\n");
        self(self, l, midVal - 1);
        self(self, midVal + 1, r);
    };    
    dfs(dfs, 1, n);
    printf("%d\n", cnt);
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)  solve();

    return 0;
}