最小交换次数使学生开心 - 算法题解

道尔顿是一个班级的老师，班级里有n个学生，编号从1到n。教室里有n个椅子，也编号从1到n。最初，学生i坐在椅子pi上。保证p1，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。

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