### ** inversions**

An inversion in a sequence *A*[1..*n*] is defined as *i*, *j*, 1 ≤ *i* < *j* ≤ *n*, such that *A*[*i*] > *A*[*j*]. For example, the sequence *A* = {1, 5, 2, 4, 3} contains 4 inversions, from the pairs (5, 2), (5, 4), (5, 3), (4, 3).

Your task is simple: Given a sequence, determine the number of inversions in the sequence.

## Input

The first line of input will be an integer *T* (*T* ≤ 100), stating the number of test cases.

*T* test cases follow, each in the following format:

First line: An integer *N* (*N* ≤ 50,000),

Next line: *N* integers, giving the values of *A*[1], *A*[2], ..., *A*[*N*]. You may assume that 0 ≤ *A*[*k*] ≤ 2,147,483,647 for all *k* ≤ *N*.

## Output

For each test case, output a single number: The number of inversions in the sequence.

## Sample Input 1

3
5
1 5 2 4 3
5
1 2 3 4 5
6
6 5 4 3 2 1

## Sample Output 1

4
0
15