时间环

题目描述

自从Orange研制出空间跃迁技术之后，人类终于能够在宇宙之中开启真正的星际旅行。这项背后的另外一个伟大成果：升维技术，这项技术背后的价值更是不可估量。利用这项技术，人类可以触及到之前从未有过的第四维度，从而实现真正的时间旅行。

原来在我们所认识的三维空间中，我们认为时间运行在一个独立于三维外的一个一维线性空间，而我们所处的三维空间是这个时间线上的一个点，这个点只会在时间线上向前做线性运动。因此我们无法触及时间，从而实现时间穿越。然而，在第四维度中，我们可以直接接触时间，并且操纵时间轴上点，从而使得我们能够获得操作时间的能力。

在第四维度中，时间的分布并不是线性的，而是呈现一种近似于布朗运动的紊乱状态。换句话说，我们在四维空间中朝某个方向前进 $1$ 个单位，所处的时间可能向前进步若干年，也可能退步若干年。这对于人类理解四维空间无疑是一个巨大的难题。

但好在Orange在不断探索下，逐渐摸清了四维空间中时间的流向：倘若我们位于时间点 $i$，我们向前移动一个单位，则会相应的来到时间点 $a_i$ (这是一个单向的过程，意味着你到达时间点 $a_i$ 之后无法再回到时间点 $i$)。我们都知道，这意味着我们可能无法探索所有的时间点，从而陷入到一个时间环中。为了解决这个问题，Orange为此研制了一种特殊的调制器，他可以交换任意两个时间点的 $a_i$。现在，Orange发现了 $n$ 个时间点，他想知道，最少要使用多少次调制器，才能让这 $n$ 个时间点相互可达。请你计算这个答案。

输入格式

第一行一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例数。

对于每个测试用例： 第一行一个整数 $\textstyle n$ ($\textstyle 1 \le n \le 10^5$)，表示时间点的数量。 第二行共 $\textstyle n$ 个整数 $\textstyle a_1, a_2, \dots, a_n$ ($\textstyle 1 \le a_i \le n$)，表示时间点 $\textstyle i$ 能够到达 时间点 $\textstyle a_i$。

保证所有测试用例的 $\textstyle n$ 之和不超过 $\textstyle 10^5$。 保证给定的 $a_i$ 是一个 $n$ 的排列。

排列：一个长度为 $n$ 的序列是一个排列，当且仅当其不重不漏的包含 $1 \sim n$ 中的所有整数。

输出格式

对于每组测试数据，输入一行，包含一个整数表示答案。

样例 #1

样例输入 #1

5
1
1
2
1 2
3
1 3 2
4
1 3 2 4
5
3 4 5 2 1

样例输出 #1

0
1
1
2
1

提示

样例解释3

对于第三组测试数据，任意交换两个时间点的 $a_i$，即可达成目标。