import java.util.*;

public class InsertionSortShiftCounter {

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int queries = Integer.parseInt(scanner.nextLine().trim());
    for (int q = 0; q < queries; q++) {
        int n = Integer.parseInt(scanner.nextLine().trim());
        int[] arr = Arrays.stream(scanner.nextLine().trim().split(" "))
                          .mapToInt(Integer::parseInt)
                          .toArray();

        long shifts = countShifts(arr);
        System.out.println(shifts);
    }

    scanner.close();
}

// Wrapper to count shifts using merge sort
private static long countShifts(int[] arr) {
    int[] temp = new int[arr.length];
    return mergeSortAndCount(arr, temp, 0, arr.length - 1);
}

// Merge sort with inversion count
private static long mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
    long count = 0;
    if (left < right) {
        int mid = (left + right) / 2;

        count += mergeSortAndCount(arr, temp, left, mid);
        count += mergeSortAndCount(arr, temp, mid + 1, right);
        count += mergeAndCount(arr, temp, left, mid, right);
    }
    return count;
}

// Merge two sorted halves and count inversions
private static long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
    long count = 0;
    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i + 1); // Count shifts
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, left, arr, left, right - left + 1);
    return count;
}

}