Junghoon Jugoon Jung Goon, in an attempt to impress Mr. White, has decided to perform a complex magic trick. He starts out by laying cards face down on a table in a straight line. Each card has a number such that the cards form some permutation of the numbers . 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 . Help him compute the minimum number of swaps required to sort the cards.
The input contains on the first line the number of test cases , . Each test case consists of two input lines. The first line of a test case contains an integer , determining the number of cards. The second line of a test case contains a permutation of the numbers through , indicating the current order of the cards.
For each test case, print the minimum number of swaps needed to sort the cards.
3 3 1 3 2 4 4 3 2 1 2 2 1
1 6 1