#include<bits/stdc++.h>
using namespace std;
long long int ans=0;
void merge(int *arr,int left,int middle,int right)
{
int i,j,k;
int n1=middle-left+1;
int n2=right-middle;
int a[n1]={0};
int b[n2]={0};
for(int i=0;i<n1;++i)
{
a[i]=arr[left+i];
}
for(int j=0;j<n2;++j)
{
b[j]=arr[j+middle+1];
}
i=0;j=0;k=left;
while(i<n1 and j<n2)
{
if(a[i]<=b[j])
{
arr[k]=a[i];
++i;
++k;
}
if(b[j]<a[i])
{
ans+=(middle-i);
arr[k]=b[j];
++j;
++k;
}
}
while(i<n1)
{
arr[k]=a[i];
++k;
++i;
}
while(j<n2)
{
arr[k]=b[j];
++j;
++k;
}
}
void merge_sort(int *arr,int first,int last)
{
if(first<last)
{
int mid=(first+last)/2;
merge_sort(arr,0,mid);
merge_sort(arr,mid+1,last);
merge(arr,first,mid,last);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int p{0};
cin>>p;
while(p)
{
int n{0};
//cout<<"Enter Size of Array\n";
cin>>n;
ans=0;
int arr[n]={0};
for(int i=0;i<n;++i)
{
cin>>arr[i];
}
merge_sort(arr,0,n-1);
cout<<ans<<"\n";
--p;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgbG9uZyBpbnQgYW5zPTA7Cgp2b2lkIG1lcmdlKGludCAqYXJyLGludCBsZWZ0LGludCBtaWRkbGUsaW50IHJpZ2h0KQp7CglpbnQgaSxqLGs7CglpbnQgbjE9bWlkZGxlLWxlZnQrMTsKCWludCBuMj1yaWdodC1taWRkbGU7CglpbnQgYVtuMV09ezB9OwoJaW50IGJbbjJdPXswfTsKCWZvcihpbnQgaT0wO2k8bjE7KytpKQoJewoJCWFbaV09YXJyW2xlZnQraV07Cgl9Cglmb3IoaW50IGo9MDtqPG4yOysraikKCXsKCQliW2pdPWFycltqK21pZGRsZSsxXTsKCX0KCWk9MDtqPTA7az1sZWZ0OwoJd2hpbGUoaTxuMSBhbmQgajxuMikKCXsKCQlpZihhW2ldPD1iW2pdKQoJCXsKCQkJYXJyW2tdPWFbaV07CgkJCSsraTsKCQkJKytrOwoJCX0KCQlpZihiW2pdPGFbaV0pCgkJewkKCQkJYW5zKz0obWlkZGxlLWkpOwoJCQlhcnJba109YltqXTsKCQkJKytqOwoJCQkrK2s7CgkJfQoJfQoJd2hpbGUoaTxuMSkKCXsKCQlhcnJba109YVtpXTsKCQkrK2s7CgkJKytpOwoJfQoJd2hpbGUoajxuMikKCXsKCQlhcnJba109YltqXTsKCQkrK2o7CgkJKytrOwoJfQp9Cgp2b2lkIG1lcmdlX3NvcnQoaW50ICphcnIsaW50IGZpcnN0LGludCBsYXN0KQp7CglpZihmaXJzdDxsYXN0KQoJewoJCWludCBtaWQ9KGZpcnN0K2xhc3QpLzI7CgkJbWVyZ2Vfc29ydChhcnIsMCxtaWQpOwoJCW1lcmdlX3NvcnQoYXJyLG1pZCsxLGxhc3QpOwoJCW1lcmdlKGFycixmaXJzdCxtaWQsbGFzdCk7Cgl9Cn0KCmludCBtYWluKCkKewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CQoJY2luLnRpZShOVUxMKTsKCWludCBwezB9OwoJY2luPj5wOwoJd2hpbGUocCkKCXsKCWludCBuezB9OwoJLy9jb3V0PDwiRW50ZXIgU2l6ZSBvZiBBcnJheVxuIjsKCWNpbj4+bjsKCWFucz0wOwoJaW50IGFycltuXT17MH07Cglmb3IoaW50IGk9MDtpPG47KytpKQoJewoJCWNpbj4+YXJyW2ldOwoJfQoJbWVyZ2Vfc29ydChhcnIsMCxuLTEpOwoJY291dDw8YW5zPDwiXG4iOwoJLS1wOwoJfQoJcmV0dXJuIDA7Cn0=