B. Перестановка Swap
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана неотсортированная перестановка $$$p_1, p_2, \ldots, p_n$$$. Чтобы отсортировать перестановку, выберите один раз целое число $$$k$$$ ($$$k \ge 1$$$) и выполните некоторые операции над перестановкой. В одной операции вы можете выбрать два целых числа $$$i$$$, $$$j$$$ ($$$1 \le j < i \le n$$$) таких, что $$$i - j = k$$$, затем поменять местами $$$p_i$$$ и $$$p_j$$$.

Какое максимальное значение $$$k$$$ вы можете выбрать, чтобы отсортировать данную перестановку?

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

Неотсортированная перестановка $$$p$$$ — это такая перестановка, что существует хотя бы одна позиция $$$i$$$, которая удовлетворяет условию $$$p_i \ne i$$$.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Затем следует их описание.

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

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

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

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

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

Мы можем показать, что ответ всегда существует.

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

В первом наборе входных данных максимальное значение $$$k$$$, которое вы можете выбрать, равно $$$1$$$. Операции, используемые для сортировки перестановки:

  • Поменять местами $$$p_2$$$ и $$$p_1$$$ ($$$2 - 1 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 3, 2]$$$
  • Поменять местами $$$p_2$$$ и $$$p_3$$$ ($$$3 - 2 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3]$$$

Во втором наборе входных данных максимальное значение $$$k$$$, которое вы можете выбрать, равно $$$2$$$. Операции, используемые для сортировки перестановки:

  • Поменять местами $$$p_3$$$ и $$$p_1$$$ ($$$3 - 1 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 4, 3, 2]$$$
  • Поменять местами $$$p_4$$$ и $$$p_2$$$ ($$$4 - 2 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3, 4]$$$