You are given an array A consisting of N distinct positive integers.

Find the smallest positive integer d such that there exists no pair of integers (i, j) (1≤ i< j ≤ N) where abs(A_{i} - A_{j}) is divisible by d. 

In other words, d \nmid abs(A_{i} - A_{j}) for all (1≤ i < j≤ N). 

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integers N — the number of the array A.
- The second line of each test case contains N space-separated distinct integers A_{1}, A_{2}, \ldots , A_{N} denoting the array A.

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

For each test case, output the smallest positive integer d such that d \nmid (A_{i} - A_{j}) for all (1≤ i < j≤ N). 

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

$1 ≤ T ≤ 1000$ 
$2 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 2 \cdot 10^{5}$
- The sums of $N$ and $max(A)$ over all test cases does not exceed $3 \cdot 10 ^ 5$.

----- Sample Input 1 ------ 
3
3
1 2 3
3
1 2 10
3
1 3 10
----- Sample Output 1 ------ 
3
5
4
----- explanation 1 ------ 
Test case $1$: The possible differences are $abs(A_{1} - A_{2}) = 1, abs(A_{1} - A_{3}) = 2, abs(A_{2} - A_{3}) = 1$. The smallest positive integer not dividing any of these differences is $3$.

Test case $2$: The possible differences are $abs(A_{1} - A_{2}) = 1, abs(A_{1} - A_{3}) = 9, abs(A_{2} - A_{3}) = 8$. The smallest positive integer not dividing any of these differences is $5$.

Test case $3$: The possible differences are $abs(A_{1} - A_{2}) = 2, abs(A_{1} - A_{3}) = 9, abs(A_{2} - A_{3}) = 7$. The smallest positive integer not dividing any of these differences is $4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Mathematics


Solutions:
import numpy.fft as fft

def coeff(p, Max):
	for i in range(19):
		if 1 << i > Max:
			break
	c = [0] * (1 << i + 1)
	for p in p:
		c[p] = 1
	return c

def invcoeff(p, Max):
	D = []
	for i in range(Max + 1, len(p)):
		if abs(p[i]) > 1e-09:
			D.append(i - Max)
	return D

def getdiffs(A):
	M = max(A)
	M_A = [M - a for a in A]
	FFT_A = fft.rfft(coeff(A, M))
	FFT_M_A = fft.rfft(coeff(M_A, M))
	return invcoeff(fft.irfft(FFT_A * FFT_M_A), M)
DIVS = [set() for N in range(2 * 10 ** 5)]
for i in range(1, 2 * 10 ** 5):
	for k in range(i, 2 * 10 ** 5, i):
		DIVS[k].add(i)

def main(N, A):
	ABS = getdiffs(A)
	DIV = set()
	for absval in ABS:
		DIV |= DIVS[absval]
	for d in range(2, 2 * 10 ** 5 + 5):
		if d not in DIV:
			return d
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	A = list(map(int, input().split()[:N]))
	print(main(N, A))