#include <bits/stdc++.h>
using namespace std;
long long c=0;
long long merge(int ar[],int low,int mid,int high)
{
int p=low,q=mid+1,k=0;
long long count=0;
int temp[high-low+1];
while(p<=mid && q<=high)
{
if(ar[p]<=ar[q])
{
temp[k++] = ar[p++];
}
else
{
count += mid-p+1;
temp[k++] = ar[q++];
}
}
while(p<=mid)
{
temp[k++] = ar[p++];
}
while(q<=high)
temp[k++] = ar[q++];
for(int i=low;i<=high;i++)
{
ar[i] = temp[i-low];
}
return count;
}
void breakArr(int ar[],int n,int low,int high)
{
if(high==low)
return;
int mid = (low+high)/2;
breakArr(ar,n,low,mid);
breakArr(ar,n,mid+1,high);
c = c + merge(ar,low,mid,high);
}
int main() {
int t,n;
cin>>t;
while(t--)
{
c=0;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
breakArr(a,n,0,n-1);
cout<<c<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpsb25nIGxvbmcgYz0wOwpsb25nIGxvbmcgbWVyZ2UoaW50IGFyW10saW50IGxvdyxpbnQgbWlkLGludCBoaWdoKQp7CglpbnQgcD1sb3cscT1taWQrMSxrPTA7Cglsb25nIGxvbmcgY291bnQ9MDsKCWludCB0ZW1wW2hpZ2gtbG93KzFdOwoJd2hpbGUocDw9bWlkICYmIHE8PWhpZ2gpCgl7CgkJaWYoYXJbcF08PWFyW3FdKQoJCXsKCQkJdGVtcFtrKytdID0gYXJbcCsrXTsKCQl9CgkJZWxzZQoJCXsKCQkJY291bnQgKz0gbWlkLXArMTsKCQkJdGVtcFtrKytdID0gYXJbcSsrXTsKCQl9Cgl9Cgl3aGlsZShwPD1taWQpCgl7CgkJdGVtcFtrKytdID0gYXJbcCsrXTsKCX0KCXdoaWxlKHE8PWhpZ2gpCgl0ZW1wW2srK10gPSBhcltxKytdOwoJZm9yKGludCBpPWxvdztpPD1oaWdoO2krKykKCXsKCQlhcltpXSA9IHRlbXBbaS1sb3ddOwoJfQoJcmV0dXJuIGNvdW50Owp9CnZvaWQgYnJlYWtBcnIoaW50IGFyW10saW50IG4saW50IGxvdyxpbnQgaGlnaCkKewoJaWYoaGlnaD09bG93KQoJcmV0dXJuOwoJaW50IG1pZCA9IChsb3craGlnaCkvMjsKCWJyZWFrQXJyKGFyLG4sbG93LG1pZCk7CglicmVha0FycihhcixuLG1pZCsxLGhpZ2gpOwoJYyA9IGMgKyBtZXJnZShhcixsb3csbWlkLGhpZ2gpOwp9CmludCBtYWluKCkgewoJaW50IHQsbjsKCWNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQljPTA7CgkJY2luPj5uOwoJCWludCBhW25dOwoJCWZvcihpbnQgaT0wO2k8bjtpKyspCgkJY2luPj5hW2ldOwoJCWJyZWFrQXJyKGEsbiwwLG4tMSk7CgkJY291dDw8Yzw8ZW5kbDsKCX0KCXJldHVybiAwOwp9