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$.

Samples

4
1
1
4
6 6 12 12
3
24 120 210
4
2 4 6 10

2
5
5
3