도서관 아르바이트는 고달프다

철수는 KAIST 중앙도서관에서 아르바이트를 한다. 부주의한 이용자들이 책상에 두고 간 책을 모아 서가의 제자리에 다시 꽂는 것이 그의 일이다. 효율적으로 일하기 위해 철수는 흩어진 책들을 자신을 위해 비워 둔 긴 서가 하나에 모두 모은 뒤, 청구기호 순서대로 정렬한다. 그런 다음 정렬된 책들을 수레에 싣고 서가 사이를 돌아다니며 각 책을 제자리에 되돌려 놓는다.

가장 힘든 일은 이 서가 위의 책들을 청구기호 순으로 정렬하는 것이다. 철수는 순서가 어긋난 두 권을 골라 서로 바꾸는 일을 모든 책이 정렬될 때까지 반복한다. 어떤 두 책은, 청구기호가 더 작은 책이 청구기호가 더 큰 책의 오른쪽에 놓여 있을 때 순서가 어긋났다고 한다.

책들을 청구기호의 오름차순으로 정렬하는 데 필요한 최소 교환 횟수를 구하는 프로그램을 작성하라.

첫 줄에는 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 서가에 놓인 책의 수 $n$이 주어지고, 둘째 줄에는 $n$개의 양의 정수가 주어지는데 $i$번째 정수는 위치 $i$에 놓인 책의 청구기호이다. 모든 청구기호는 서로 다르며, 각각은 $10{,}000$ 이하이다. 또한 $n$은 $1{,}000$ 이하이다.

$t$개의 정수를 한 줄에 공백 하나로 구분하여 출력한다. $i$번째 정수는 $i$번째 테스트 케이스에서 책을 정렬하는 데 필요한 최소 교환 횟수이다.