A. Easy Peasy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ positive integers. Insert a minimum non-negative number $$$x \neq 1$$$ in the array, such that the greatest common divisor of all the $$$n + 1$$$ elements becomes $$$1$$$.

Input

The first line consists a number $$$t$$$ which shows the number of testcases.

$$$$$$1 \le t \le 10^4$$$$$$

In the first line of each testcase you'll be given an integer $$$n$$$ which shows the length of the array.

$$$$$$1 \le n \le 10^5$$$$$$

In the second line you'll receive $$$n$$$ positive integers.

$$$$$$1 \le a_i \le 10^{18}$$$$$$

It is guaranteed that sum of $$$n$$$ overall testcases does not exceed $$$10^5$$$.

Output

Print the minimum non-negative integer $$$x \neq 1$$$ such that after insertion the gcd of all the elements of the array becomes $$$1$$$.

Example
Input
2
3
21 14 49
3
33 3 11
Output
2
0