13651365 SUSTech Online Judge
Problem 1365 --[Medium I] Bubble Sort

1365: [Medium I] Bubble Sort

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1357  Solved: 269
[Submit][Status][Web Board]

Description

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. He leaves the puzzle to you. Could you solve it?


Notice that: In Bubble Sort Algorithm, you can only swap adjacent elements.

Input

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.

Output

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

Sample Input

1
4
4 1 2 3

Sample Output

3

HINT

Source

 

[Submit][Status]