Directi Q2

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time.

Given below is pseudocode of insertion sort algorithm applied on array A (zero-based indexing).
        def compare(a, b) :
            if a > b return 1
            else return -1

        for i : 1 to length(A)
	    j = i - 1
	    while j > 0
               if compare(A[j-1], A[j]) > 0
                    swap(A[j], A[j-1])
                    j = j - 1
               else break

Given an array A of distinct integers , find difference between number of compare function calls and number of swap function calls by above algorithm when applied on A.


Let us take an example with A = {1, 2, 4, 3}. If we apply insertion sort as above on A we call sequeunce of compare and swap functions in following order

    compare (A[0], A[1])
    compare (A[1], A[2])
    compare (A[2], A[3])
    swap       (A[2], A[3])
    compare (A[1], A[2])


Here compare function is called 4 times, swap function is called 1 time. The answer is 4-1 = 3.
Input

The first line of the input contains an integer T denoting the number of test cases.T test cases follow
The first line of each test case contains a single integer N denoting length of array A.
The second line of each test case contains N space-separated distinct integers A0, A1, ..., AN-1denoting the elements of A.
Output

For each test case, output a single line containing difference between number of compare function calls and number of swap function calls.
Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 10000
1 ≤ A[i] ≤ N
Example

Input:
6
2
1 2
2
2 1
4
1 2 4 3
4
2 3 1 4
4
4 3 2 1
10
5 3 2 4 1 6 7 9 8 10

Output:
1
0
3
2
0
6
Explanation

Example test case 1.
For A = {1, 2} following is the sequence of compare and swap functions called.

    compare (A[0], A[1])

Hence answer is 1 for first test case.


Example test case 2.
For A = {2, 1} following is the sequence of compare and swap functions called.

    compare (A[0], A[1])
    swap       (A[0], A[1])


Hence answer is 0 for second test case.

Example test case 4.
For A = {2, 3, 1, 4} following is the sequence of compare and swap functions called.

    compare (A[0], A[1])
    compare (A[1], A[2])
    swap       (A[1], A[2])
    compare (A[0], A[1])
    swap       (A[0], A[1])
    compare (A[2], A[3])


Hence answer is 2 for fourth test case.
note--O(n^2) fails..