D. Lucky Permutationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a permutation^\dagger p of length n.In one operation, you can choose two indices 1 \le i < j \le n and swap p_i with p_j.Find the minimum number of operations needed to have exactly one inversion^\ddagger in the permutation.^\dagger A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).^\ddagger The number of inversions of a permutation p is the number of pairs of indices (i, j) such that 1 \le i < j \le n and p_i > p_j.InputThe first line contains a single integer t (1 \le t \le 10^4) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer n (2 \le n \le 2 \cdot 10^5).The second line of each test case contains n integers p_1,p_2,\ldots, p_n (1 \le p_i \le n). It is guaranteed that p is a permutation.It is guaranteed that the sum of n over all test cases does not exceed 2 \cdot 10^5.OutputFor each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.ExampleInput
422 121 243 4 1 242 4 3 1Output
0
1
3
1
NoteIn the first test case, the permutation already satisfies the condition.In the second test case, you can perform the operation with (i,j)=(1,2), after that the permutation will be [2,1] which has exactly one inversion.In the third test case, it is not possible to satisfy the condition with less than 3 operations. However, if we perform 3 operations with (i,j) being (1,3),(2,4), and (3,4) in that order, the final permutation will be [1, 2, 4, 3] which has exactly one inversion.In the fourth test case, you can perform the operation with (i,j)=(2,4), after that the permutation will be [2,1,3,4] which has exactly one inversion.
422 121 243 4 1 242 4 3 1
0 1 3 1 
['constructive algorithms', 'dfs and similar', 'graphs', 'greedy', '*1800']