E. Сакурако, Косукэ и перестановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Экзамены Сакурако закончились, она справилась на отлично. В награду она получила перестановку $$$p$$$. Косукэ был не совсем доволен, потому что он провалил один экзамен и не получил подарок. Он решил пробраться в её комнату (спасибо за код от её замка) и испортить перестановку так, чтобы она стала простой.

Перестановка $$$p$$$ считается простой, если для каждого $$$i$$$ $$$(1\le i \le n)$$$ выполняется одно из условий:

  • $$$p_i=i$$$
  • $$$p_{p_i}=i$$$

Например, перестановки $$$[1, 2, 3, 4]$$$, $$$[5, 2, 4, 3, 1]$$$ и $$$[2, 1]$$$ являются простыми, а $$$[2, 3, 1]$$$ и $$$[5, 2, 1, 4, 3]$$$ — нет.

За одну операцию Косукэ может выбрать индексы $$$i,j$$$ $$$(1\le i,j\le n)$$$ и поменять местами элементы $$$p_i$$$ и $$$p_j$$$.

Сакурако вот-вот вернется домой. Ваша задача — вычислить минимальное количество операций, которые необходимо выполнить Косукэ, чтобы сделать перестановку простой.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных описывается двумя строками.

  • Первая строка содержит одно целое число $$$n$$$ ($$$1\le n \le 10^6$$$) — длину перестановки $$$p$$$.
  • Вторая строка содержит $$$n$$$ целых чисел $$$p_i$$$ ($$$1\le p_i\le n$$$) — элементы перестановки $$$p$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Гарантируется, что $$$p$$$ является перестановкой.

Выходные данные

Для каждого набора входных данных выведите минимальное количество операций, которые необходимо выполнить Косукэ, чтобы перестановка стала простой.

Пример
Входные данные
6
5
1 2 3 4 5
5
5 4 3 2 1
5
2 3 4 5 1
4
2 3 4 1
3
1 3 2
7
2 3 1 5 6 7 4
Выходные данные
0
0
2
1
0
2
Примечание

В первом и втором примерах перестановки уже простые.

В четвёртом примере достаточно поменять местами $$$p_2$$$ и $$$p_4$$$. Таким образом перестановка станет равна $$$[2, 1, 4, 3]$$$ за $$$1$$$ операцию.