#include<bits/stdc++.h>
using namespace std;
#define f0(i,n) for(int i = 0;i<n;i++)
#define f1(i,n) for(int i = 1;i<=n;i++)
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define ll long long
#define  sc(n) scanf("%d",&n)
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MAX = 1e6+6;
int a[MAX];
int n;
ll ct = 0;
void merged(int l,int r,int mid)
{
    int i, j, k;
    i = l;
    j = mid+1;
    k = 0;
   int * temp = new int[r-l+1];
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++]= a[j++];
            ct+=(mid+1-i);
        }
    }
    while(i<=mid)
    {
        temp[k++]= a[i++];
    }
    while(j<=r)
    {
        temp[k++]= a[j++];
    }
    k=0;
    for(i = l;i<=r;i++)
    {
        a[i] = temp[k++];
    }
    delete(temp);

}
void divide(int l ,int r)
{
    if(l<r)
    {
        int mid = (l+r)/2;
       divide(l,mid);
       divide(mid+1,r);
       merged(l,r,mid);

    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
    cin>>n;
    for(int i =0;i<n;i++)
    {
        cin>>a[i];
    }

    divide(0,n-1);
    cout<<ct<<endl;
        ct=0;

    }

}