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.