You have N books numbered uniquely, placed randomly on a shelf. You want to arrange the books in ascending order of their numbers.
The only operation allowed is swap any two books. Your task is to determine the minimum number of swaps needed to sort the shelf.
First line: an integer T, the number of test cases.
For each test case:
First line: integer N, the number of books.
Second line: N space-separated integers representing book numbers on the shelf.
For each test case, print the minimum number of swaps required to organize the bookshelf.
1 ≤ T ≤ 20
2 ≤ N ≤ 10⁵
1 ≤ Book Number ≤ 10⁹
All book numbers are distinct.
| Example Input | Example Output |
|---|---|
2 4 4 3 2 1 5 1 5 4 3 2 |
2 2 |
Test Case 1: Books [4,3,2,1] can be sorted with 2 swaps: swap 4↔1, swap 3↔2.
Test Case 2: Books [1,5,4,3,2] can be sorted with 2 swaps: swap 5↔2, swap 4↔3.