Minimum Swaps to Sort Permutation

You are given a permutation of the numbers from 1 to N. Your task is to determine the minimum number of swap operations required to sort this permutation in ascending order. A swap operation consists of choosing two indices and exchanging their values.

This problem can be solved using the concept of cycle detection in a permutation. If you can decompose the permutation into disjoint cycles, the minimum number of swaps needed to sort that cycle is equal to \(\text{cycle length} - 1\). The total number of swaps is the sum of swaps needed for each cycle.

Input/Output Format:

The input is read from standard input (stdin) and the output is to be written to standard output (stdout).

inputFormat

The first line of input contains an integer T, the number of test cases. For each test case, the first line contains an integer N representing the number of elements in the permutation. The second line contains N space-separated integers denoting the permutation.

outputFormat

For each test case, output a single integer on a new line denoting the minimum number of swaps required to sort the given permutation in ascending order.## sample

4
5
4 3 2 5 1
4
1 3 2 4
6
6 5 4 3 2 1
1
1

3
1
3
0