You have an array a� of n� non-negative integers. Let’s define f(a,x)=[a1modx,a2modx,…,anmodx]�(�,�)=[�1mod�,�2mod�,…,��mod�] for some positive integer x�. Find the biggest x�, such that f(a,x)�(�,�) is a palindrome.
Here, amodx�mod� is the remainder of the integer division of a� by x�.
An array is a palindrome if it reads the same backward as forward. More formally, an array a� of length n� is a palindrome if for every i� (1≤i≤n1≤�≤�) ai=an−i+1��=��−�+1.
Lunatic Never Content Solution Codeforces
The first line contains a single integer t� (1≤t≤1051≤�≤105) — the number of test cases.
The first line of each test case contains a single integer n� (1≤n≤1051≤�≤105).
The second line of each test case contains n� integers ai�� (0≤ai≤1090≤��≤109).
It’s guaranteed that the sum of all n� does not exceed 105105.
Lunatic Never Content Solution Codeforces
For each test case output the biggest x�, such that f(a,x)�(�,�) is a palindrome. If x� can be infinitely large, output 00 instead.
Example
4
2
1 2
8
3 0 1 2 0 3 2 1
1
0
3
100 1 1000000000
Lunatic Never Content Solution Codeforces
In the first example, f(a,x=1)=[0,0]�(�,�=1)=[0,0] which is a palindrome.
In the second example, f(a,x=2)=[1,0,1,0,0,1,0,1]�(�,�=2)=[1,0,1,0,0,1,0,1] which is a palindrome.
It can be proven that in the first two examples, no larger x� satisfies the condition.
In the third example, f(a,x)=[0]�(�,�)=[0] for any x�, so we can choose it infinitely large, so the answer is 00.