Lunatic Never Content Solution Codeforces

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 (1in1≤�≤�ai=ani+1��=��−�+1.

Lunatic Never Content Solution Codeforces

The first line contains a single integer t (1t1051≤�≤105) — the number of test cases.

The first line of each test case contains a single integer n (1n1051≤�≤105).

The second line of each test case contains n integers ai�� (0ai1090≤��≤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.

Leave a Comment