题目描述

给定一个无序的排列 $p_1, p_2, ..., p_n$。你可以选择一个常量 $k\ (k \ge 1)$ 并且对这个排列做一些操作使得该排列有序。在一次操作中，你可以选择两个整数 $i, j (1 \le j < i \le n)$，然后交换 $p_i$ 和 $p_j$，其中 $i - j = k$。

对于给定的排列，请你求出满足条件的 $k$ 的最大值。

输入格式

每个测试点包含多组测试样例。测试点第一行一个整数 $t\ (1 \le t \le 10^4)$，表示测试样例的组数。

每组样例第一行一个整数 $n\ (2 \le n \le 10^5)$，表示排列的长度。第二行 $n$ 个整数，表示给定的排列。

保证所有测试样例的总长度不超过 $2 \times 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) \to p = [1, 3, 2]$
• 交换 $p_2$ 和 $p_3 (3 - 2 = 1) \to p = [1, 2, 3]$

对于第二组样例，满足条件的 $k$ 的最大值是 $2$。使得给定排列有序的操作如下：

• 交换 $p_3$ 和 $p_1 (3 - 1 = 2) \to p = [1, 4, 3, 2]$
• 交换 $p_4$ 和 $p_2 (4 - 2 = 2) \to p = [1, 2, 3, 4]$