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