310581: CF1855A. Dalton the Teacher

A. Dalton the Teachertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Dalton is the teacher of a class with $n$ students, numbered from $1$ to $n$. The classroom contains $n$ chairs, also numbered from $1$ to $n$. Initially student $i$ is seated on chair $p_i$. It is guaranteed that $p_1,p_2,\dots, p_n$ is a permutation of length $n$.

A student is happy if his/her number is different from the number of his/her chair. In order to make all of his students happy, Dalton can repeatedly perform the following operation: choose two distinct students and swap their chairs. What is the minimum number of moves required to make all the students happy? One can show that, under the constraints of this problem, it is possible to make all the students happy with a finite number of moves.

A permutation of length $n$ 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).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of students.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — $p_i$ denotes the initial chair of student $i$. It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output the minimum number of moves required.

ExampleInput

5
2
2 1
3
1 2 3
5
1 2 5 4 3
4
1 2 4 3
10
10 2 1 3 6 5 4 7 9 8

Output

0
2
2
1
1

Note

In the first test case, both students are already happy, so Dalton can perform $0$ moves.

In the second test case, Dalton can swap the chairs of students $1$ and $2$ to get the array $[2, 1, 3]$. Then he can swap chairs of students $2$ and $3$ to get the array $[2, 3, 1]$. At this point all the students are happy, and he performed $2$ moves. It is impossible to perform the task with fewer moves.

In the third test case, by swapping the chairs of students $1$ and $2$ and then swapping the chairs of students $4$ and $5$, Dalton gets the array $[2, 1, 5, 3, 4]$ in $2$ moves.

题目大意：
Dalton是一个有n个学生的老师，学生编号从1到n。教室里有n张椅子，编号也是从1到n。最初，学生i坐在椅子p_i上。保证p_1, p_2, ..., p_n是一个长度为n的排列。

如果学生的编号和椅子的编号不同，那么这个学生就是快乐的。为了让所有学生都快乐，Dalton可以反复进行以下操作：选择两个不同的学生并交换他们的椅子。求使所有学生都快乐所需的最小移动次数。可以证明，在这个问题的约束下，可以通过有限的移动次数使所有学生都快乐。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 10^5），表示学生的数量。
- 第二行包含n个整数p_1, p_2, ..., p_n（1 ≤ p_i ≤ n），其中p_i表示学生i的初始椅子。保证p是一个排列。
- 保证所有测试用例的n之和不超过10^5。

输出：
- 对于每个测试用例，输出使所有学生都快乐所需的最小移动次数。

示例：
输入：
```
5
2
2 1
3
1 2 3
5
1 2 5 4 3
4
1 2 4 3
10
10 2 1 3 6 5 4 7 9 8
```
输出：
```
0
2
2
1
1
```
注意：
- 在第一个测试用例中，两个学生都已经快乐，所以Dalton可以执行0次移动。
- 在第二个测试用例中，Dalton可以通过交换学生1和学生2的椅子，然后交换学生2和学生3的椅子，使得所有学生都快乐，共进行了2次移动。无法用更少的移动次数完成任务。
- 在第三个测试用例中，通过交换学生1和学生2的椅子，然后交换学生4和学生5的椅子，Dalton在2次移动内得到了排列[2, 1, 5, 3, 4]。题目大意： Dalton是一个有n个学生的老师，学生编号从1到n。教室里有n张椅子，编号也是从1到n。最初，学生i坐在椅子p_i上。保证p_1, p_2, ..., p_n是一个长度为n的排列。 如果学生的编号和椅子的编号不同，那么这个学生就是快乐的。为了让所有学生都快乐，Dalton可以反复进行以下操作：选择两个不同的学生并交换他们的椅子。求使所有学生都快乐所需的最小移动次数。可以证明，在这个问题的约束下，可以通过有限的移动次数使所有学生都快乐。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 10^5），表示学生的数量。 - 第二行包含n个整数p_1, p_2, ..., p_n（1 ≤ p_i ≤ n），其中p_i表示学生i的初始椅子。保证p是一个排列。 - 保证所有测试用例的n之和不超过10^5。 输出： - 对于每个测试用例，输出使所有学生都快乐所需的最小移动次数。 示例： 输入： ``` 5 2 2 1 3 1 2 3 5 1 2 5 4 3 4 1 2 4 3 10 10 2 1 3 6 5 4 7 9 8 ``` 输出： ``` 0 2 2 1 1 ``` 注意： - 在第一个测试用例中，两个学生都已经快乐，所以Dalton可以执行0次移动。 - 在第二个测试用例中，Dalton可以通过交换学生1和学生2的椅子，然后交换学生2和学生3的椅子，使得所有学生都快乐，共进行了2次移动。无法用更少的移动次数完成任务。 - 在第三个测试用例中，通过交换学生1和学生2的椅子，然后交换学生4和学生5的椅子，Dalton在2次移动内得到了排列[2, 1, 5, 3, 4]。