A. Учитель Дальтон
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дальтон — учитель класса, в котором учатся $$$n$$$ учеников, пронумерованных от $$$1$$$ до $$$n$$$. В классе имеется $$$n$$$ стульев, также пронумерованных от $$$1$$$ до $$$n$$$. Изначально студент $$$i$$$ сидит на стуле $$$p_i$$$. Гарантируется, что $$$p_1,p_2,\dots, p_n$$$ — перестановка длины $$$n$$$.

Студент счастлив, если его номер отличается от номера его стула. Чтобы сделать всех студентов счастливыми, Дальтон может многократно проделать следующую операцию: выбрать двух разных студентов и поменять их стулья местами. Какое минимальное количество ходов необходимо для того, чтобы все студенты были счастливы? Можно показать, что при ограничениях этой задачи можно сделать всех студентов счастливыми за конечное число ходов.

Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, расположенных в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается в массиве дважды), и $$$[1,3,4]$$$ также не является перестановкой ($$$n=3$$$, но в массиве есть $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит единственное целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество студентов.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p_i$$$ обозначает начальную кафедру студента $$$i$$$. Гарантируется, что $$$p$$$ является перестановкой.

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

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

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

Пример
Входные данные
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
Выходные данные
0
2
2
1
1
Примечание

В первом наборе входных данных оба студента уже счастливы, поэтому Дальтон может сделать $$$0$$$ ходов.

Во втором наборе входных данных Дальтон может поменять местами стулья студентов $$$1$$$ и $$$2$$$, получив массив $$$[2, 1, 3]$$$. Затем он может поменять местами стулья студентов $$$2$$$ и $$$3$$$, получив массив $$$[2, 3, 1]$$$. В этот момент все студенты довольны, а он выполнил $$$2$$$ хода. Выполнить задачу меньшим числом ходов невозможно.

В третьем наборе входных данных, поменяв местами стулья студентов $$$1$$$ и $$$2$$$, а затем поменяв местами стулья студентов $$$4$$$ и $$$5$$$, Дальтон за $$$2$$$ хода получил массив $$$[2, 1, 5, 3, 4]$$$.