~~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.

#### Input Specification

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.

#### 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
```

## Comments

just counting the number of inversions in the array should be sufficient right .

Where do these questions come from-what is the VMSS 7 week challenge, and where is it run?

See also Train Swapping.

Hey Jas, just a heads up we typically don't point these things out; it's not really good etiquette. It doesn't really help anyone. Still, good observation, I'm sure many people would just miss the similarity! ;)