给你一个未排序的排列p1，p2，…，pn。为了对排列进行排序，你可以选择一个正整数k (k≥1)，并对排列进行以下操作若干次，最终使得排列有序递增。在一次操作中，你可以选择两个整数i, j(1≤j<i≤n)，满足i−j=k（即两个元素的位置间隔为k），然后交换pi和pj的值。

请问，对于一个给定的未排序的排列p，按照上述操作完成排列的排序，你可以选择的k值最大是多少?

说明1：排列是由1到n 共n个不同的整数以任意顺序组成的序列。例如，[2,3,1,5,4]是一个排列，但[1,2,2]不是一个排列(因为2在序列中出现两次)，[1,3,4]也不是一个排列(n=3，但序列中有4，确实2)。

说明2：一个未排序的排列p是这样一个排列：至少有一个位置i满足pi≠i。

第一行一个整数t(1 ≤t≤ 10000)：测试样例数。

对于每个测试样例：

第一行一个整数n（2≤n≤1e5）:n为排列的长度；

       第二行为n个整数p1,p2,…,pn(1≤pi≤n):排列p的n个元素值；

       测试数据确保排列p是未排序的排列。

    对于每个测试样例，输出一行一个整数k，为可以完成排序的最大间隔k；

对于第一个测试用例：序列p=[3,1,2]，可以选择k=1，则操作如下：

第一次选择i=2，j=1，交换p2，p1，则序列转换为:[1,3,2];

第二次选择i=3，j=2，交换p3，p2，则序列转换为:[1,2,3];

我们再也找不到比1大的k值完成对序列的排序；

对于第二个测试用例：序列p=[3,4,1,2]，可以选择k=2，则操作如下：

第一次选择i=3，j=1，交换p3，p1，则序列转换为:[1,4,3,2];

第二次选择i=4，j=2，交换p4，p2，则序列转换为:[1,2,3,4];

我们再也找不到比2大的k值完成对序列的排序；

天梯赛#107-zxs2020