Junghoon Jugoon Jung Goon, in an attempt to impress Mr. White, has decided to perform a complex magic trick. He starts by laying ~L~ ~(0 \le L \le 60)~ cards face down on a table in a straight line. Each card has a number such that the ~L~ cards form some permutation of the numbers ~1, 2, \dots, L~. However, since Jung Goon has a photographic memory, he knows the exact order of his cards. His trick involves making a series of swaps, where he switches the positions of two adjacent cards. Since he is a computer science student, he wishes to use as few swaps as possible to sort the line of cards into the order ~1, 2, \dots, L~. Help him compute the minimum number of swaps required to sort the cards.

Input Specification

The input contains on the first line the number of test cases ~N~ ~(1 \le N \le 10)~. Each test case consists of two input lines. The first line of a test case contains an integer ~L~, determining the number of cards. The second line of a test case contains a permutation of the numbers ~1~ through ~L~, indicating the current order of the cards.

Output Specification

For each test case, print the minimum number of swaps needed to sort the cards.

Sample Input

3
3
1 3 2
4
4 3 2 1
2
2 1

Sample Output

1
6
1