def sort_pair(arr0, arr1):
    if len(arr0) > len(arr1):
        return arr1, arr0
    else:
        return arr0, arr1
    
def merge(arr0, arr1):
    inversions = 0
    result = []
    while len(arr0) > 0 and len(arr1) > 0:
        if arr0[0] <= arr1[0]:
            result.append(arr0.pop(0))
        else:
            # count the inversion right here: add the length of left array
            inversions += len(arr0)
            result.append(arr1.pop(0))
            
    if len(arr0) == 0:
        result += arr1
    elif len(arr1) == 0:
        result += arr0
        
    return result, inversions

def sort(arr):
    length = len(arr)
    mid = length//2
    if length >= 2:
        sorted_0, counts_0 = sort(arr[:mid])
        sorted_1, counts_1 = sort(arr[mid:])
        result, counts = merge(sorted_0, sorted_1)
        return result, counts + counts_0 + counts_1
    else:
        return arr, 0

def count_inversions(a):
    final_array, inversions = sort(a)
    # print(final_array)
    return inversions
      

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    print(count_inversions(arr))

def merge(arr, left_half, right_half):
    i, j, k = 0, 0, 0
    inversions = 0
    left_len, right_len = len(left_half), len(right_half)
    while i < left_len and j < right_len:
        if left_half[i] <= right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
            inversions += left_len - i
        k += 1

    while i < left_len:
        arr[k] = left_half[i]
        i, k = i+1, k+1

    while j < right_len:
        arr[k] = right_half[j]
        j, k = j+1, k+1

    return inversions

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        left_half, right_half = arr[:mid], arr[mid:]

        inversions = merge_sort(left_half) + merge_sort(right_half) + merge(arr, left_half, right_half)
        return inversions
    return 0

def countInversions(arr):
    return merge_sort(arr)

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        n = int(input().strip())
        arr = list(map(int, input().strip().split(' ')))
        print(countInversions(arr))

def countInversions(arr):
    res = [0] * len(arr)

    return merge(arr, res, 0, len(arr)-1)


def merge(arr, res, left, right):
    if left >= right:
        return 0

    inversions = 0

    left_end = (left + right) // 2
    right_start = left_end + 1

    inversions += merge(arr, res, left, left_end)
    inversions += merge(arr, res, right_start, right)
    inversions += mergeHalf(arr, res, left, right)
    return inversions


def mergeHalf(arr, res, left, right):
    if left >= right:
        return 0

    inversions = 0

    left_end = mid = (left + right) // 2
    right_start = right_beg = left_end + 1
    left_beg = index = left

    while left <= left_end and right_start <= right:
        pt1 = arr[left]
        pt2 = arr[right_start]

        if pt1 <= pt2:
            res[index] = pt1
            index += 1
            left += 1
        else:
            res[index] = pt2
            index += 1
            inversions += mid - left + 1
            right_start += 1

    while left <= left_end:
        res[index] = arr[left]
        left += 1
        index += 1

    while right_start <= right:
        res[index] = arr[right_start]
        right_start += 1
        index += 1


    arr[left_beg:left_end + 1] = res[left_beg:left_end + 1]
    arr[right_beg:right + 1] = res[right_beg: right + 1]

    return inversions

def Merge_and_CountSplitInv(left_half, right_half):

    i = 0
    j = 0
    splitInv = 0

    B = []

    while i < len(left_half) and j < len(right_half):

        if left_half[i] <= right_half[j]:
            B.append(left_half[i])
            i += 1
        else:
            B.append(right_half[j])
            j += 1
            splitInv += (len(left_half) - i)

    B += left_half[i:]
    B += right_half[j:]

    return B, splitInv


def Sort_and_CountInv(A):

    # base case
    if len(A) < 2:
        return A, 0

    # divide the list into two
    mid = len(A) // 2

    left = A[:mid]      # recursively sort first half of A
    right = A[mid:]     # recursively sort second half of A

    x, leftInv = Sort_and_CountInv(left)
    y, rightInv = Sort_and_CountInv(right)
    z, splitInv = Merge_and_CountSplitInv(x, y)

    return z, leftInv + rightInv + splitInv

long countInversions(vector<int> arr) {
    long inversions = 0;

    const int bits = 24;
    vector<unordered_map<int, long>> counts(bits);
    for (auto iter = arr.crbegin(); iter < arr.crend(); iter++) {
        int item = *iter;
        // Read counts.
        { // scope
            int copy = item;
            for (int shifted = 0; shifted < bits; ++shifted) {
                if ((copy & 1) > 0)
                    inversions += counts[shifted][copy - 1];
                copy >>= 1;
            }
        }

        // Add to counts.
        { // scope
            int copy = item;
            for (int shifted = 0; shifted < bits; ++shifted) {
                counts[shifted][copy]++;
                copy >>= 1;
            }
        }
    }

    return inversions;
}

from bisect import bisect_right, insort

# Complete the countInversions function below.
def countInversions(arr):
    inversions = len(arr)*(len(arr)-1)//2
    left = []
    for idx, v in enumerate(arr):
        v_idx = bisect_right(left, v)
        inversions -= v_idx
        insort(left, v)
    return inversions

count += mid + 1 - i;

count += countInversions(aux, lo, mid, arr);
count += countInversions(aux, mid + 1, hi, arr);

def merge(left, right):
    counter = 0
    result = []  # final result array, that is an empty array
 
#create two indices and initialize with 0
    i,j = 0,0

    ra = result.append
    lenl = len(left)
    lenr = len(right)
 
# Till this condition is true, keep on appending elements into resultant array
    while (i<lenl) and (j<lenr):
        if left[i] <= right[j]:
            ra(left[i]) #append ith element of left into resultant array
            i+=1
        else:
            ra(right[j])  #append jth element of right into resultant array
            j+=1
            counter += lenl-i  #COUNT HERE!
 
# it is basically specifies that if any element is remaining in the left array from -
# ith to the last index so that it should appended into the resultant array. And similar -
# to the right array.
    result += left[i:]
    result += right[j:]
    return result, counter
 
# Definition for merge sort
# this takes an input list

def mergesort(lst):
        
    if(len(lst)<= 1): # this means that the list is already sorted.
        return lst, 0
    mid = (len(lst)//2)

            # Define definition for merge which basically takes two arrays i.e., the left and right part


     
# left array will be mergesort applied over the list from starting index 
# till the mid index
    left, counter0 = mergesort(lst[:mid])
 
# right array will be mergesort applied recursively over the list from mid index
# till the last index 
    right, counter1 = mergesort(lst[mid:])

    result, counter2 = merge(left,right)
 
    return result, counter2 + counter0 + counter1

def countInversions(arr):
    
    #Idea: Count the number of transpositions needed when you apply the mergesort to arr.


    final, counter = mergesort(arr)

    return counter