Manhattan Sort
Yet another sorting problem! In this one, you’re given a sequence S of N distinct integers and are asked to sort it with minimum cost using only one operation:
The Manhattan swap!
Let S_i and S_j be two elements of the sequence at positions i and j respectively, applying the Manhattan swap operation to S_i and S_j swaps both elements with a cost of |i-j|. For example, given the sequence {9, 5, 3}, we can sort the sequence with a single Manhattan swap operation by swapping the first and last elements for a total cost of 2 (absolute difference between positions of 9 and 3).
Input
The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 ≤ N ≤ 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 bit signed integer.
Output
For each test case, output one line containing a single integer, the minimum cost of sorting the sequence using only the Manhattan swap operation.