题目描述

给定一个整数 $n$ 和一个长度为 $n$ 的数组 $a=[a_1,a_2,\dots,a_n]$。

请你找出最小的整数 $x$（$2\le x\le 10^{18}$），使得存在一个下标 $i$（$1\le i\le n$）满足 $\gcd(a_i,x)=1$。如果区间 $[2,10^{18}]$ 内不存在这样的 $x$，则输出 $-1$。

这里 $\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量（$1\le t\le 10^4$）。

接下来有 $t$ 个测试用例，每个测试用例包含两行：

• 第一行包含一个整数 $n$，数组长度（$1\le n\le 10^5$）。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^{18}$）。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数：所求的最小的 $x$（如果存在且 $2\le x\le 10^{18}$），否则输出 $-1$。

样例输入

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

样例输出

2
5
5
3

说明

样例解释

在第一个测试用例中， $\gcd(2,1)=1$ ，这是满足条件的最小数字。

在第二个测试用例中：

• $\gcd(2,6)=2$ 、 $\gcd(2,12)=2$ ，因此 $2$ 不能作为答案。
• $\gcd(3,6)=3$ 、 $\gcd(3,12)=3$ ，因此 $3$ 不能作为答案。
• $\gcd(4,6)=2$ 、 $\gcd(4,12)=4$ ，因此 $4$ 不能作为答案。
• $\gcd(5,6)=1$ ，所以答案是 $5$ 。

在第三个测试用例中：

• $\gcd(2,24)=2$ 、 $\gcd(2,120)=2$ 、 $\gcd(2,210)=2$ ，因此 $2$ 不能作为答案。
• $\gcd(3,24)=3$ 、 $\gcd(3,120)=3$ 、 $\gcd(3,210)=3$ ，因此 $3$ 不能作为答案。
• $\gcd(4,24)=4$ 、 $\gcd(4,120)=4$ 、 $\gcd(4,210)=2$ ，因此 $4$ 不能作为答案。
• $\gcd(5,24)=1$ ，所以答案是 $5$ 。

在第四个测试用例中：

• $\gcd(2,2)=2$ 、 $\gcd(2,4)=2$ 、 $\gcd(2,6)=2$ 、 $\gcd(2,10)=2$ ，因此 $2$ 不能作为答案。
• $\gcd(3,2)=1$ ，所以答案是 $3$ 。