Codeforces Round 870 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

number theory

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Lunatic Never Content

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have an array $$$a$$$ of $$$n$$$ non-negative integers. Let's define $$$f(a, x) = [a_1 \bmod x, a_2 \bmod x, \dots, a_n \bmod x]$$$ for some positive integer $$$x$$$. Find the biggest $$$x$$$, such that $$$f(a, x)$$$ is a palindrome.

Here, $$$a \bmod x$$$ 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 \leq i \leq n$$$) $$$a_i = a_{n - i + 1}$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$).

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^5$$$.

Output

For each test case output the biggest $$$x$$$, such that $$$f(a, x)$$$ is a palindrome. If $$$x$$$ can be infinitely large, output $$$0$$$ instead.

Example

Input

421 283 0 1 2 0 3 2 1103100 1 1000000000

Output

1 2 0 999999900

Note

In the first example, $$$f(a, x = 1) = [0, 0]$$$ which is a palindrome.

In the second example, $$$f(a, x = 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]$$$ for any $$$x$$$, so we can choose it infinitely large, so the answer is $$$0$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 19:41:30 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|