You are given an unsorted permutation P of size N. An operation is defined as:

Swap P_{i} and P_{i+K} for any i in the range [1,N-K].

Find the maximum value of K, such that, the permutation P can be sorted by applying any finite number of operations.

Note that, a permutation of size N contains all integers from 1 to N exactly once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N, the size of permutation.
- The next line contains N integers describing the permutation P.
- It is guaranteed that the given permutation is not sorted.

------ Output Format ------ 

For each test case, output on a new line the maximum possible value of K.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
3
4
4 2 3 1
5
1 4 3 2 5
2
2 1

----- Sample Output 1 ------ 
3
2
1

----- explanation 1 ------ 
- Test Case $1$: Permutation can be sorted by swapping $P_{1}$ and $P_{4}$. So, the maximum possible value of $K$ is $3$. It can be shown that we cannot sort the permutation for any $K> 3$.

- Test Case $2$: Swapping $P_{2}$ and $P_{4}$ will sort the permutation. So, the maximum possible value of $K$ is $2$. It can be shown that we cannot sort the permutation for any $K> 2$.

- Test Case $3$: Swapping $P_{1}$ and $P_{2}$ will sort the permutation. So, the maximum possible value of $K$ is $1$. It can be shown that we cannot sort the permutation for any $K> 1$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(1, n + 1):
		l[i - 1] = abs(l[i - 1] - i)
	hcf = l[0]
	for j in range(1, n):
		hcf = math.gcd(hcf, l[j])
	print(hcf)


import math
for ii in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(n):
		if l[i] != i + 1:
			l1.append(abs(l[i] - i - 1))
	if l1 == []:
		print(0)
	elif len(l1) == 1:
		print(l1[0])
	elif len(l1) == 2:
		print(math.gcd(l1[0], l1[1]))
	else:
		a = math.gcd(l1[0], l1[1])
		for i in range(2, len(l1)):
			a = math.gcd(a, l1[i])
		print(a)


import math
tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = math.gcd(ans, abs(a[i] - (i + 1)))
	print(ans)


def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[p[i]] = i + 1
	a = []
	for i in d.keys():
		if i != d[i]:
			a.append(abs(i - d[i]))
	g = 0
	for i in range(len(a)):
		g = computeGCD(g, a[i])
	print(g)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = 0
	for i in range(n):
		m = math.gcd(m, abs(l[i] - (i + 1)))
	print(m)


import math
n = int(input())
for _ in range(n):
	n1 = int(input())
	x = list(map(int, input().split()))
	x = list(enumerate(x))
	y = sorted(x, key=lambda z: z[1])
	z = 0
	for i in range(n1):
		k = abs(y[i][0] - x[i][0])
		z = math.gcd(z, k)
	print(z)


import math
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	count = 0
	for i in range(n):
		count = math.gcd(count, abs(p[i] - (i + 1)))
	print(count)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	fv = 0
	lv = 0
	l = [int(i) for i in input().split()]
	sl = []
	ans = 0
	for i in range(n):
		if i + 1 != l[i]:
			ans = gcd(ans, abs(l[i] - (i + 1)))
	print(ans)


from math import gcd
a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	a = 0
	for j in range(0, len(c)):
		a = gcd(abs(j + 1 - c[j]), a)
	print(a)


import math
T = int(input())
while T > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	lst = [x for x in range(1, n + 1)]
	dic = dict()
	r = 0
	for i in range(n):
		r = abs(arr[i] - lst[i])
		if r not in dic:
			dic[r] = 1
	gcd = r
	for i in dic.keys():
		gcd = math.gcd(i, gcd)
	print(gcd)
	T -= 1


import numpy as np
from collections import Counter

def find_GCD(numbers):
	if len(numbers) == 1:
		return numbers[0]
	else:
		baseline = min(numbers)
		remainings = numbers % baseline
		together = np.append(remainings[remainings != 0], baseline)
		return find_GCD(together)
T = int(input())
for tc in range(T):
	size = int(input())
	per = input().split(' ')
	per = np.array(list(map(int, per)))
	stand = np.array(range(1, size + 1))
	dif = abs(per - stand)
	freq = Counter(dif)
	del freq[0]
	print(find_GCD(np.array(list(freq.keys()))))


import math
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for (i, j) in enumerate(l):
		l1.append(j - (i + 1))
	print(reduce(math.gcd, l1))


def g(n, m):
	if m == 0:
		return n
	return g(m, n % m)
for i in range(int(input())):
	x = int(input())
	li = list(map(int, input().split()))
	m = 0
	for j in range(x):
		a = abs(li[j] - (j + 1))
		m = g(m, a)
	print(m)


T = int(input())
vector = lambda x, t: [t(num) for num in x.split()]
from math import gcd
for _ in range(T):
	n = int(input())
	nums = vector(input(), int)
	g = 0
	for (a, b) in zip(nums, sorted(nums)):
		if a != b:
			g = gcd(abs(a - b), g)
	print(g)


def gcd(a, b):
	if b == 0:
		return a
	aprime = a % b
	return gcd(b, aprime)
for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	diffs = []
	for i in range(len(p)):
		if p[i] != i + 1:
			diffs.append(abs(p[i] - 1 - i))
	a = diffs[0]
	for i in range(1, len(diffs)):
		a = gcd(a, diffs[i])
	print(a)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	i = 0
	num = []
	while i < n:
		if arr[i] - i - 1:
			num.append(abs(arr[i] - i - 1))
		i += 1
	gcd = num[0]
	for i in num[1:]:
		while i:
			(gcd, i) = (i, gcd % i)
	print(gcd)


def hcfnaive(a, b):
	if b == 0:
		return abs(a)
	else:
		return hcfnaive(b, a % b)
a = int(input())
for i in range(a):
	n = int(input())
	l = list(map(int, input().split()))
	res = []
	for i in range(n):
		if abs(l[i] - 1 - i) > 0:
			res.append(abs(l[i] - 1 - i))
	answer = res[0]
	for i in range(len(res) - 1):
		answer = hcfnaive(answer, res[i + 1])
	print(answer)


try:
	import math
	t = int(input())
	for i in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		a = 0
		for i in range(n):
			a = math.gcd(a, abs(l[i] - (i + 1)))
		print(a)
except:
	pass


import math
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for i in range(n):
		k = math.gcd(k, i + 1 - a[i])
	print(k)
	t = t - 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = math.gcd(ans, i + 1 - l[i])
	print(ans)


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
for ti in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ls = []
	ls1 = []
	cnt = 0
	flag = 0
	for i in range(n):
		ls.append(abs(arr[i] - (i + 1)))
	num1 = ls[0]
	num2 = ls[1]
	gcd = find_gcd(num1, num2)
	for i in range(2, len(ls)):
		gcd = find_gcd(gcd, ls[i])
	print(gcd)


import math
for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 0
	for j in range(n):
		ans = math.gcd(ans, j + 1 - p[j])
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	dist = []
	for i in range(len(arr)):
		curr_pos = i
		actual_pos = arr[i] - 1
		dist.append(abs(curr_pos - actual_pos))
	k = dist[0]
	for i in range(1, len(dist)):
		k = math.gcd(k, dist[i])
	print(k)


def find_gcd(a, b):
	if b == 0:
		return abs(a)
	else:
		return find_gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	unsorted_a = list(map(int, input().split()))
	num1 = 0
	for j in range(n):
		num2 = abs(unsorted_a[j] - (j + 1))
		res = find_gcd(num1, num2)
		num1 = res
	print(res)


from math import gcd as __gcd
for test in range(int(input())):
	n = int(input())
	arr = [int(char) for char in input().split()]
	sorted1 = 0
	for i in range(n):
		l = abs(arr[i] - i - 1)
		sorted1 = __gcd(sorted1, l)
	print(sorted1)


import math
for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	l.insert(0, 0)
	ans = 0
	for i in range(1, a + 1):
		ans = math.gcd(ans, abs(l[i] - i))
	print(ans)


from math import gcd

def solve(nums):
	if len(nums) == 1:
		return nums[0]
	div = gcd(nums[0], nums[1])
	if len(nums) == 2:
		return div
	for i in range(1, len(nums) - 1):
		div = gcd(div, nums[i + 1])
		if div == 1:
			return div
	return div
a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	d = list.copy(c)
	d.sort()
	e = []
	for j in range(0, len(d)):
		if c[j] - d[j] != 0:
			e.append(abs(c[j] - d[j]))
	print(solve(e))


from math import gcd

def solve():
	n = int(input())
	li = list(map(int, input().split()))
	ans = 0
	for i in range(len(li)):
		ans = gcd(abs(li[i] - (i + 1)), ans)
	print(ans)
for _ in range(int(input())):
	solve()


import math
t = int(input())
for i in range(t):
	p = int(input())
	li = list(map(int, input().split()))
	li1 = li[:]
	li1.sort()
	li2 = []
	for j in range(p):
		li2.append(abs(j + 1 - li[j]))
	ans = 0
	for k in range(len(li2)):
		ans = math.gcd(ans, li2[k])
	print(ans)


import math
for i in range(int(input())):
	y = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(y):
		ans = math.gcd(ans, i + 1 - l[i])
	print(ans)


import math
for _ in range(int(input())):
	tot = int(input())
	a = [int(i) for i in input().split()]
	res = 0
	for i in range(tot):
		if a[i] - i - 1:
			if not res:
				res = abs(a[i] - i - 1)
			else:
				res = math.gcd(res, a[i] - i - 1)
	print(res)


from functools import reduce

def gcd(x, y):
	if x == 0:
		return y
	return gcd(y % x, x)
for t in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	A = [abs(P[i - 1] - i) for i in range(1, N + 1)]
	print(reduce(gcd, A))


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for i in range(n):
		if l[i] != i + 1:
			a.append(abs(l[i] - (i + 1)))
	ans = 0
	for i in a:
		ans = math.gcd(ans, i)
	print(ans)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = list()
	for i in range(n - 1):
		if a[i] == i + 1:
			continue
		else:
			l.append(abs(1 + i - a[i]))
	g = l[0]
	for i in range(len(l)):
		g = gcd(g, l[i])
	print(g)


import math
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	l = l[:n]
	ans = 0
	for i in range(len(l)):
		ans = math.gcd(ans, l[i] - i - 1)
	print(ans)


import math
for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	ans = 0
	for i in range(N):
		temp = abs(P[i] - i - 1)
		ans = math.gcd(ans, temp)
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	k = abs(l1[0] - 1)
	for i in range(1, n):
		k = math.gcd(k, abs(l1[i] - (i + 1)))
	print(k)


import math

def solution():
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(1, n + 1):
		ans = math.gcd(ans, abs(l[i - 1] - i))
	print(ans)
t = int(input())
for i in range(t):
	solution()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if nums[i] - i - 1:
			if not ans:
				ans = abs(nums[i] - i - 1)
			else:
				ans = gcd(ans, nums[i] - i - 1)
	print(ans)


import math
for i in range(int(input())):
	a = int(input())
	arr = list(map(int, input().split(' ')))
	max_array = []
	for i in range(a):
		max_array.append(abs(arr[i] - (i + 1)))
	hcf = max_array[0]
	for i in range(1, len(max_array)):
		hcf = math.gcd(hcf, max_array[i])
	print(hcf)


import math
for _ in range(int(input())):
	n = int(input())
	x = [int(x) for x in input().split(' ')]
	y = sorted(x)
	s = 0
	h = []
	for (i, j) in enumerate(x):
		if j != y[i]:
			h.append(abs(j - y[i]))
	for i in range(len(h)):
		s = math.gcd(s, h[i])
	print(s)


import math
t = int(input())
for _ in range(t):
	tmp = []
	n = int(input())
	l1 = list(map(int, input().split()))
	for i in range(n):
		if l1[i] != i + 1:
			tmp.append(abs(l1[i] - i - 1))
	ans = tmp[0]
	l = len(tmp)
	for i in range(1, l):
		ans = math.gcd(ans, tmp[i])
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = []
	for i in range(n):
		if arr[i] != i + 1:
			temp.append(abs(arr[i] - i - 1))
	ans = temp[0]
	l = len(temp)
	for i in range(1, l):
		ans = math.gcd(ans, temp[i])
	print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		ans = gcd(ans, abs(l[i] - (i + 1)))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	i = 0
	for ctr in arr:
		import math
		ans = math.gcd(ans, ctr - (i + 1))
		i = i + 1
	print(ans)


from math import gcd
t = int(input())
while t:
	n = int(input())
	p = [int(x) for x in input().split()]
	ans = p[0] - 1
	for i in range(n):
		ans = gcd(ans, abs(p[i] - i - 1))
	print(ans)
	t -= 1


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def main():
	for _ in range(int(input())):
		N = int(input())
		arr = list(map(int, input().split()))
		res = []
		for i in range(N):
			v = abs(arr[i] - i - 1)
			if v != 0:
				res.append(v)
		g = res[0]
		for i in res[1:]:
			g = gcd(g, i)
		print(g)
main()


import math
for i in range(int(input())):
	num = int(input())
	lis = list(map(int, input().split(' ')))
	gc = abs(1 - lis[0])
	for j in range(2, num + 1):
		num1 = abs(lis[j - 1] - j)
		gc = math.gcd(gc, num1)
	print(gc)


import math
for t in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		ans = math.gcd(ans, arr[i] - i - 1)
	print(ans)


T = int(input())
import math
for vinay in range(T):
	N = int(input())
	P = list(map(int, input().split()))
	flag = [0] * (N + 1)
	for i in range(N):
		flag[P[i]] = i + 1
	ans = 0
	for i in range(1, N + 1):
		ans = math.gcd(ans, i - flag[i])
	print(ans)


import math
t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	flag = 0
	ans = 0
	for i in range(0, len(list1)):
		if list1[i] != i + 1:
			if flag == 0:
				ans = abs(list1[i] - 1 - i)
				flag = 1
			else:
				g = abs(list1[i] - 1 - i)
				ans = math.gcd(ans, g)
				if ans == 1:
					break
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	ans = 0
	for i in range(n):
		ans = math.gcd(ans, i + 1 - a[i])
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	new = [0 for i in range(n)]
	ans = []
	for i in range(n):
		if arr[i] != i + 1:
			new[i] = arr[i]
		else:
			continue
	for i in range(n):
		if new[i] > 0:
			v = abs(new[i] - (i + 1))
			ans.append(v)
		else:
			continue
	g = ans[0]
	for j in ans:
		g = math.gcd(g, j)
	print(g)


import math
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	dic = {}
	for j in range(n):
		dic[lst[j]] = j
	arr = []
	for j in range(n):
		ele = lst[j]
		ind = dic[j + 1]
		ad = abs(ele - j - 1)
		arr.append(ad)
	g = arr[0]
	for j in arr:
		g = math.gcd(g, j)
	print(g)


from math import gcd
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for i in range(N):
		ans = gcd(ans, abs(A[i] - 1 - i))
	print(ans)


test = int(input())
case = 0
while case < test:
	n = int(input())
	nums = list(map(lambda x: int(x), input().split()))
	k = None
	i = 1
	while i <= n:
		if nums[i - 1] == i:
			pass
		else:
			temp = abs(nums[i - 1] - i)
			if k == None:
				k = temp
			else:
				hcf = min(temp, k)
				while hcf > 1:
					if k % hcf == 0 and temp % hcf == 0:
						break
					hcf -= 1
				k = hcf
				if k == 1:
					break
		i += 1
	print(k)
	case += 1


import math
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = [0] * (n + 1)
	max1 = 0
	for j in range(len(x)):
		y[x[j]] = j + 1
	for j in range(1, n + 1):
		max1 = math.gcd(max1, abs(j - y[j]))
	print(max1)


def gcd(a, b):
	if a == b:
		return a
	(a, b) = (min(a, b), max(a, b))
	if b % a == 0:
		return a
	else:
		while b % a != 0:
			t = b % a
			b = a
			a = t
		return t
for _ in range(int(input())):
	n = int(input())
	l = []
	a = list(map(int, input().split()))
	for i in range(n):
		if a[i] != i + 1:
			l.append(abs(a[i] - (i + 1)))
	c = l[0]
	for i in l:
		c = gcd(c, i)
		if c == 1:
			break
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.copy()
	a.sort()
	d = {}
	d1 = {}
	for i in range(len(l)):
		d[l[i]] = i
		d1[a[i]] = i
	t = []
	for i in range(len(a)):
		if d1[a[i]] - d[a[i]] == 0:
			continue
		else:
			t.append(d1[a[i]] - d[a[i]])
	gcd = math.gcd(t[0], t[1])
	for i in range(2, len(t)):
		gcd = math.gcd(gcd, t[i])
	print(gcd)


import math
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	k_max = 0
	for i in range(n):
		k_max = math.gcd(k_max, i + 1 - lst[i])
	print(k_max)


from math import gcd

def solve(nums):
	if len(nums) == 1:
		return nums[0]
	div = gcd(nums[0], nums[1])
	if len(nums) == 2:
		return div
	for i in range(1, len(nums) - 1):
		div = gcd(div, nums[i + 1])
		if div == 1:
			return div
	return div
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	l = arr.copy()
	l.sort()
	ans = []
	for i in range(n):
		ans.append(abs(l[i] - arr[i]))
	print(solve(ans))


from math import gcd

def solve(li, N):
	d = 0
	for (ind, el) in enumerate(li):
		diff = abs(el - ind - 1)
		d = gcd(d, diff)
	return d
for case in range(int(input())):
	N = int(input())
	li = list(map(int, input().split()))
	print(solve(li, N))


import math
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr = arr[::-1]
	k = n
	ans = []
	for i in range(n):
		if arr[i] != k:
			ans.append(abs(n - i - arr[i]))
		k = k - 1
	num1 = ans[0]
	num2 = ans[1]
	gcd = math.gcd(num1, num2)
	for i in range(2, len(ans)):
		gcd = math.gcd(gcd, ans[i])
		if gcd == 1:
			break
	print(gcd)


import math
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	k = 0
	for i in range(n):
		if p[i] != i + 1:
			if not k:
				k = abs(i + 1 - p[i])
				continue
			k = math.gcd(k, abs(i + 1 - p[i]))
	print(k)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = []
	per = [i for i in range(1, n + 1)]
	for i in range(n):
		if per[i] != a[i]:
			d.append(abs(per[i] - a[i]))
	ans = d[0]
	for i in range(1, len(d)):
		ans = math.gcd(ans, d[i])
	print(ans)


import sys, math
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] = abs(a[i] - 1 - i)
	ans = 0
	for i in range(n):
		ans = math.gcd(ans, a[i])
	return ans
for _ in range(int(input())):
	print(solve())


import math
t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().strip().split()))
	res = 0
	for i in range(n):
		res = math.gcd(res, abs(p[i] - i - 1))
	print(res)