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

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