Problem D: Bubble Sort

Problem D: Bubble Sort

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3758  Solved: 742
[Submit][Status][Web Board]


Vince is curious about how many swap times does Bubble Sort need to sort an array. He implements Bubble Sort Algorithm within 0.000001 second and gets the answer. Now, he wants to find a more efficient way to calculate.  Could you solve it?

In Bubble Sort algorithm, you can only swap adjacent elements.


The first line will be an integer T (1 ≤ T ≤10), which is the number of test cases.

For each test case, the first line will be an integer n (1 ≤ n ≤ 105) showing the length of array. Then there are n integers. It is guarenteed that each number will not exceed the limit of int.


For each case, please output the swap times that Bubble Sort needs to sort the array.

Sample Input

4 1 2 3

Sample Output