C. Омкар и бейсбол
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Патрик любит играть в бейсбол, но иногда он тратит так много часов на пробежки, что его разум начинает затуманиваться! Патрик уверен, что его набранные очки за $$$n$$$ игр соответствуют тождественной перестановке (т.е. в первой игре он набирает $$$1$$$, во второй игре он набирает $$$2$$$ и так далее). Однако, когда он посмотрел на свои записи, он увидел, что все значения перепутаны!

Определим специальный обмен следующим образом: выберите любой подмассив очков и переставьте местами его элементы так, чтобы ни один элемент не оказался в той же позиции, где он был до обмена. Например, выполнение специального обмена на $$$[1,2,3]$$$ может дать $$$[3,1,2]$$$, но не может дать $$$[3,2,1]$$$, так как $$$2$$$ находится в той же позиции.

Вам дана перестановка из $$$n$$$ целых чисел. Пожалуйста, помогите Патрику найти минимальное количество специальных обменов, необходимых для того, чтобы сделать ее отсортированной! Можно доказать, что при данных ограничениях это число не превышает $$$10^{18}$$$.

Массив $$$a$$$ является подмассивом массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$, удалив несколько (возможно, ноль или все) элементов из начала и несколько (возможно, ноль или все) элементов с конца.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$). Описание наборов входных данных приведено ниже.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — длину данной перестановки.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{1},a_{2},...,a_{n}$$$ ($$$1 \leq a_{i} \leq n$$$)  — начальную перестановку.

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

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

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

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

Первая перестановка она уже отсортирована, поэтому обмены не нужны.

Можно показать, что для сортировки второй перестановки нужно как минимум $$$2$$$ обмена.

$$$[3, 2, 4, 5, 1, 6, 7]$$$

Сделаем специальный обмен для диапазона ($$$1, 5$$$)

$$$[4, 1, 2, 3, 5, 6, 7]$$$

Сделаем специальный обмен для диапазона ($$$1, 4$$$)

$$$[1, 2, 3, 4, 5, 6, 7]$$$