#include<algorithm>
#include<vector>
#include<cstdio>
#include<map>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<iomanip>
#include<stdlib.h>
#include<set>
#include<cmath>
#define lowbit(i) (i&-i)
using namespace std;
const int N=3e5+10,inf=0x7fffffff,mod=1e9+7;
int t;
int n;
int a[N];
int stk[N];
int top=0;
int c[N];
struct giao{
    int l;
    int r;
    bool operator < (const giao &temp) const{
        return temp.r-temp.l>r-l;
    }
};
priority_queue<giao> que;
vector<int> wei[N];
int sum[N];
int get_sum(int t){
    int res=0;
    while(t){
        res+=sum[t];
        t-=lowbit(t);
    }
    return res;
}
void add(int t,int k){
    while(t<=n){
        sum[t]+=k;
        t+=lowbit(t);
    }
}
signed main(){
    cin>>t;
    while(t--){
        memset(stk,0,sizeof(stk));top=0;
        memset(c,0,sizeof(c));
        memset(sum,0,sizeof(sum));
        memset(wei,0,sizeof(wei));
        int ans=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            wei[a[i]].push_back(i);
            if(!c[a[i]]){
                c[a[i]]=1;
                stk[++top]=a[i];
            }
        }
        for(int i=1;i<=top;i++){
            int num=stk[i];
            for(int j=0;(j+1)*2<=wei[num].size();j++)
                que.push({wei[num][j],wei[num][wei[num].size()-j-1]});
        }
        while(!que.empty()){
            giao hd=que.top();
            que.pop();
            ans+=hd.r-hd.l-get_sum(hd.r)+get_sum(hd.l);
            add(hd.l,1);
            add(hd.r,1);
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
2
7
1 2 1 1 2 1 2
12
1 2 3 1 2 3 1 2 3 1 2 3
 
 
 
 1 1 2
 */