/*
Statement:
==========
Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.
Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.
Output

For every test output one line giving the number of inversions of A.
Example

Input:

2

3
3
1
2

5
2
3
8
6
1


Output:

2
5
*/
#include <stdio.h>
#include <stdlib.h>
long long int count, *a;
void merge(int,int,int);
void f(int l,int r)
{
  if(l<r)
  {
    int mid=(l+r)/2;
    f(l,mid);
    f(mid+1,r);
    merge(l,mid,r);
  }
}
void merge(int l,int mid,int r)
{
  int temp[r-l+1],i=l,j=mid+1,k=0;
  while(i<=mid && j<=r)
  {
    if(a[i]>a[j] && i<=mid)
    {
      count+=1+mid-i;
      temp[k]=a[j];
      j++;
      k++;
    }
    else
    {
      temp[k]=a[i];
      i++;
      k++;
    }
  }
  while(i<=mid)temp[k++]=a[i++];
  while(j<=r)temp[k++]=a[j++];
  for(i=0;i<=r-l;i++)
  {
    a[l+i]=temp[i];
  }
}
int main()
{
  int t;
  scanf("%d\n", &t);
  while(t--)
  {
    int n;
    count=0;
    scanf("%d",&n );
    a=(long long int*)malloc(sizeof (long long int)*n);
    for(int i=0;i<n;i++)scanf("%lld",&a[i] );
    f(0,n-1);
    printf("%lld\n", count);
  }
}