image.png

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    public static long countInversions(int[] arr){
        return mergeSort(arr,0,arr.length-1);
    }
    
    public static long mergeSort(int[] arr, int start, int end){
        if(start==end) return 0;
        long count=0;
        int mid = (start+end)/2;
        count += mergeSort(arr,start,mid); // mergeSort left and count inversions
        count += mergeSort(arr,mid+1,end); // mergeSort right and count inversions
        count += merge(arr,start,end); // merge left and right and count inversions
        return count;
    }
    public static long merge(int[] arr, int start, int end){
        long count = 0;
        int[] newarr = new int[end-start+1];
        int mid = (start+end)/2;
        int i=start,j=mid+1,p=0;
        while(i<=mid && j<=end){
            if(arr[i]>arr[j]){
                newarr[p++]=arr[j++];
                count += mid-i+1;//tricky part
            }else{
                newarr[p++]=arr[i++];
            }
        }
        // leftovers
        while(i<=mid){
            newarr[p++]=arr[i++];
        }
        while(j<=end){
            newarr[p++]=arr[j++];
        }
        System.arraycopy(newarr, 0, arr, start, end-start+1);
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int arr_i = 0; arr_i < n; arr_i++){
                arr[arr_i] = in.nextInt();
            }
            long result = countInversions(arr);
            System.out.println(result);
        }
        in.close();
    }
}