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 ≤ 10

^{5}) 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.