#include <bits/stdc++.h>

template<typename T, std::size_t N> std::istream& operator>>(std::istream& is, std::array<T, N>& v) { for (auto& i : v) is >> i; return is; }
template<typename T, std::size_t N> std::ostream& operator<<(std::ostream& os, std::array<T, N>& v) { for (auto& i : v) os << i << ' '; return os; }
template<typename T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& i : v) is >> i; return is; }
template<typename T> std::ostream& operator<<(std::ostream& os, std::vector<T>& v) { for (auto& i : v) os << i << ' '; return os; }
template<typename...Args> void debug(Args...args) { ((std::cerr << args << ' '), ...); std::cerr << '\n'; }
template<typename...Args> void println(Args...args) { ((std::cout << args << ' '), ...); std::cout << '\n'; }

using i64 = long long;

int res = 0;

int work(std::vector<int>& a, int l, int r) {
    int m = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (true) {
        i++, j--;
        while (a[i] < m) {
            i++;
        }
        while (a[j] > m) {
            j--;
        }

        if (i >= j) {
            return j;
        }
        else {
            std::swap(a[i], a[j]);
            res++;
        }
    }
    return -1;
}

void quickSort(std::vector<int>& a, int l, int r) {
    if (l >= 0 && r >= 0 && l < r) {
        int m = work(a, l, r);
        quickSort(a, l, m);
        quickSort(a, m + 1, r);
    }
}

auto solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        a[i]--;
    }

    quickSort(a, 1, n);
    std::cout << res << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int c = 1;
    std::cin >> c;

    for (int i = 1; i <= c; i++) {
        res = 0;
        solve();
    }

    return 0;
}