Work at a Library Is Tough

Chulsoo works part-time at the KAIST Central Library. His job is to gather the books that careless visitors leave lying on the desks and return them to their correct spots on the shelves. To work efficiently, he first collects the stray books onto a single long shelf that is kept empty for him, sorts them by call number, then loads the sorted pile onto a cart and walks the stacks, putting each book back where it belongs.

The hardest part is sorting the books on that shelf. Chulsoo repeatedly picks two books that are out of order and swaps them, and he keeps doing this until every book is in order. Two books are out of order when a book with a smaller call number sits somewhere to the right of a book with a larger call number.

Write a program that determines the minimum number of swaps Chulsoo needs to arrange the books in ascending order of call number.

The first line contains an integer $t$, the number of test cases. Each test case is given on two lines. The first line contains an integer $n$, the number of books on the shelf. The second line contains $n$ positive integers, where the $i$-th integer is the call number of the book currently at position $i$. All call numbers are distinct, and each is at most $10{,}000$. Also, $n$ is at most $1{,}000$.

Print $t$ integers on a single line, separated by single spaces. The $i$-th integer is the minimum number of swaps needed to sort the books in the $i$-th test case.