题目描述

给定一个未排序的排列 $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$ 的 $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$。

可以证明答案总是存在。

说明/提示

在第一个测试用例中，你能选择的最大 $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]$

由 ChatGPT 4.1 翻译

样例

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