#include <bits/stdc++.h>

using namespace std;

const int N = 1005, INF = 0x3f3f3f3f;

int n, a[N];
int fl[N], fr[N];
int buf[N * 2], *cnt = buf + N;
int f[N];

inline void Solve()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++ ) f[i] = INF;
    f[0] = 0;
    for(int i = 2; i < n; i ++ )
    {
        for(int j = 1; j <= n; j ++ ) fl[j] = fr[j] = 0;
        for(int l = i - 1, r = i + 1; l >= 1 && r <= n; l -- , r ++ )
        {
            for(int i = l + 1; i < r; i ++ )
            {
                fl[i] += a[i] < a[l];
                fr[i] += a[i] < a[r];
                fr[l] += a[l] < a[i];
                fl[r] += a[r] < a[i];
            }
            int w = 0;
            for(int i = -(r - l + 1); i <= (r - l + 1); i ++ )
            {
                cnt[i] = 0;
            }
            for(int i = l; i <= r; i ++ )
            {
                w += fl[i];
                cnt[fr[i] - fl[i]] ++ ;
            }
            cnt[0] -- ;
            int k = r - i;
            for(int i = -(r - l + 1); i <= (r - l + 1) && k; i ++ )
            {
                cnt[i] = min(cnt[i], k);
                w += i * cnt[i];
                k -= cnt[i];
            }
            // printf("![%d %d] -> %d\n", l, r, w);
            if(w > n / 3 + 10) break;
            f[r] = min(f[r], f[l - 1] + w);
        }
    }
    printf("%d\n", f[n]);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T -- ) Solve();
    return 0;
}