题目描述

给定整数 $n$ 和长度为 $n$ 的数组 $a$。

求最小整数 $x$，满足 $2 \le x \le 10^{18}$，并且存在下标 $i\;(1 \le i \le n)$，使得 $\gcd(a_i,x)=1$。

若区间 $[2,10^{18}]$ 内不存在满足条件的 $x$，输出 -1。

$\gcd(u,v)$ 表示 $u,v$ 的最大公约数。

输入格式

第一行一个整数 $t\;(1 \le t \le 10^4)$，代表测试用例数量。

每组测试用例：

• 第一行：整数 $n\;(1 \le n \le 10^5)$
• 第二行：$n$ 个整数 $a_1,a_2,\dots,a_n\;(1 \le a_i \le 10^{18})$

保证所有测试用例的 $\sum n \le 10^5$。

输出格式

对每组测试用例输出一行一个整数：满足要求的最小 $x$；无解输出 -1。

样例输入

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

样例输出

2
5
5
3

样例解释

1. 第1组：$\gcd(2,1)=1$，最小合法 $x=2$。
2. 第2组：
   • $x=2$：所有数都和2不互质，不行；
   • $x=3$：所有数都和3不互质，不行；
   • $x=4$：所有数都和4不互质，不行；
   • $x=5$：$\gcd(5,6)=1$，合法，答案为5。
3. 第3组：
   • $x=2,3,4$ 均不满足；
   • $x=5$：$\gcd(5,24)=1$，答案为5。
4. 第4组：
   • $x=2$：全部偶数，不满足；
   • $x=3$：$\gcd(3,2)=1$，答案为3。