题目描述

Dalton 是一位老师，他有 n 名学生，学生的编号为 1～n，教室里有 n 把椅子，椅子的编号也是 1～n。一开始学生 i 坐在凳子 pi 上，可以保证 p1, p2, …, pn 是一个长度为 n 的排列。

如果一个学生的编号与他（她）的椅子编号不相同，那么学生就会高兴。为了让所有学生都开心，Dalton 可以将两个不同的学生交换椅子的编号。要让所有学生开心，至少需要多少次交换？保证题目有解。

长度为 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 ≤ 10^5)，表示学生人数。
• 第二行一共 n 个整数 p1, p2, …, pn (1 ≤ pi ≤ n)，表示学生 i 的初始椅子编号。

保证所有测试用例的 n 总和不超过 10^5。

输出格式

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

输入样例 #1

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

输出样例 #1

0
2
2
1
1