11861186 SUSTech Online Judge
Problem 1186 --Sort the array[Medium]

1186: Sort the array[Medium]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 673  Solved: 124
[Submit][Status][Web Board]

Description

Hong wants you to sort a given array.  Hong is good at sorting, so he wants to make it more difficult.

Each time, you can only choose two adjacent elements and swap them.

Hong wants to know how many swaps do you need at least to make the array in ascending order.


Input

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

For each test data:

The first line contains one integer N (1≤N≤10^5) — the number of the integers.

The next line contains N integers Ai(1≤Ai≤10^9).

Output

For each case, please print the least swap you need to make the array in ascending order.

Sample Input

1
4
4 1 2 3

Sample Output

3

HINT

Source

Sorting 

[Submit][Status]