CF 1855A - Dalton the Teacher

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 pi. It is guaranteed that 1,p2,…,pn

 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 ermutation, 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≤t≤1000). The description of the test cases follows.

The first line contains a single integer n (2≤n≤105) — the number of students.

The second line contains n integers p1,p2,…,pn (1≤pi≤n) — pi 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 105.

Output

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

--------------------------------------------

道尔顿是一个班的老师，班上有n名学生，编号从1到n。 教室里有n把椅子，编号也从1到n。 最初，学生 i 坐在椅子 pi 上。 保证 1,p2,…,pn

  是长度为n的排列。

如果学生的号码与他/她的椅子的号码不同，他/她会很高兴。 为了让所有的学生都高兴，道尔顿可以重复执行以下操作：选择两个不同的学生并交换他们的椅子。 最少需要多少步才能让所有学生都满意？ 可以证明，在这个问题的约束下，有可能通过有限数量的动作让所有学生都满意。

长度为 n 的排列是由 n 个从 1 到 n 的不同整数以任意顺序组成的数组。 例如，[2,3,1,5,4]是排列，但[1,2,2]不是排列（2在数组中出现两次），并且[1,3,4]也不是排列 排列（n=3，但数组中有 4 个）。

输入

每个测试包含多个测试用例。 第一行包含测试用例的数量 t (1≤t≤1000)。 测试用例的描述如下。

第一行包含一个整数 n (2≤n≤105) — 学生人数。

第二行包含 n 个整数 p1,p2,…,pn (1≤pi≤n) — pi 表示学生 i 的初始主席。 保证p是一个排列。

保证所有测试用例的n之和不超过105。

输出

对于每个测试用例，输出所需的最小移动次数。

----------------------------------------

当位置跟序号一样的时候，记录下来，最后看一样的有多少，如果一样的是偶数个，那么就除以2即可，如果是奇数个，那么就除以2+1，当然如果都不一样，返回0即可，下面是代码：