You are given an integer $$$n$$$ and an array $$$a$$$ of length $$$n$$$.

Find the smallest integer $$$x$$$ ($$$2 \le x \le 10^{18}$$$) such that there exists an index $$$i$$$ ($$$1 \le i \le n$$$) with $$$\gcd$$$$$$^{\text{∗}}$$$$$$(a_i, x) = 1$$$. If no such $$$x$$$ exists within the range $$$[2,10^{18}]$$$, output $$$-1$$$.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input

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

Each of the following $$$t$$$ test cases consists of two lines:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the length of the array.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).

It is guaranteed that the total sum of $$$n$$$ across all test cases does not exceed $$$10^{5}$$$.

Output

For each test case, output a single integer: the smallest $$$x$$$ ($$$2 \le x \le 10^{18}$$$) such that there exists an index $$$i$$$ with $$$\gcd(a_i, x) = 1$$$. If there is no such $$$x$$$ in the range $$$[2,10^{18}]$$$, print $$$-1$$$.

Note

In the first test case, $$$\gcd(2,1)=1$$$, which is the smallest number satisfying the condition.

In the second test case:

$$$\gcd(2,6)=2$$$, $$$\gcd(2,12)=2$$$, so $$$2$$$ cannot be the answer.
$$$\gcd(3,6)=3$$$, $$$\gcd(3,12)=3$$$, so $$$3$$$ cannot be the answer.
$$$\gcd(4,6)=2$$$, $$$\gcd(4,12)=4$$$, so $$$4$$$ cannot be the answer.
$$$\gcd(5,6)=1$$$, so the answer is $$$5$$$.

In the third test case:

$$$\gcd(2,24)=2$$$, $$$\gcd(2,120)=2$$$, $$$\gcd(2,210)=2$$$, so $$$2$$$ cannot be the answer.
$$$\gcd(3,24)=3$$$, $$$\gcd(3,120)=3$$$, $$$\gcd(3,210)=3$$$, so $$$3$$$ cannot be the answer.
$$$\gcd(4,24)=4$$$, $$$\gcd(4,120)=4$$$, $$$\gcd(4,210)=2$$$, so $$$4$$$ cannot be the answer.
$$$\gcd(5,24)=1$$$, so the answer is $$$5$$$.

In the fourth test case:

$$$\gcd(2,2)=2$$$, $$$\gcd(2,4)=2$$$, $$$\gcd(2,6)=2$$$, $$$\gcd(2,10)=2$$$, so $$$2$$$ cannot be the answer.
$$$\gcd(3,2)=1$$$, so the answer is $$$3$$$.

Yet Another Array Problem

Examples