问题 C: Sort4

Given a permutation$\textstyle ^\dagger$ of length $\textstyle n$. In one operation, you can choose **at most** four elements from the permutation and swap their positions arbitrarily. What is the minimum number of operations required to sort the permutation in ascending order? $\textstyle ^\dagger$ A permutation of length $\textstyle n$ is an array consisting of $\textstyle n$ distinct integers from $\textstyle 1$ to $\textstyle n$ in arbitrary order. For example, $\textstyle [2,3,1,5,4]$ is a permutation, but $\textstyle [1,2,2]$ is not a permutation ($\textstyle 2$ appears twice in the array), and $\textstyle [1,3,4]$ is also not a permutation ($\textstyle n=3$ but there is $\textstyle 4$ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $\textstyle t$ ($\textstyle 1 \leq t \leq 10^5$). The description of the test cases follows. The first line of each test case contains an integer $\textstyle n$ ($\textstyle 1 \leq n \leq 10^6$), indicating the length of the permutation. The second line contains a permutation $\textstyle a_1, a_2, \ldots, a_n$. It is guaranteed that the sum of $\textstyle n$ across all test cases does not exceed $\textstyle 10^6$.

For each test case, output a single integer, indicating the minimum number of operations required to sort the permutation.