给定一个整数 $$$n$$$ 和一个长度为 $$$n$$$ 的数组 $$$a$$$。
找到 最小 整数 $$$x$$$ ($$$2 \le x \le 10^{18}$$$) 使得存在索引 $$$i$$$ ($$$1 \le i \le n$$$) $$$\gcd$$$$$$^{\text{*}}$$$$$$(a_i, x) = 1$$$。如果$$$[2,10^{18}]$$$范围内不存在这样的$$$x$$$,则输出$$$-1$$$。
$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
输入
第一行包含一个整数 $$$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}$$$) 使得存在索引 $$$i$$$ 且 $$$\gcd(a_i, x) = 1$$$。如果$$$[2,10^{18}]$$$范围内不存在这样的$$$x$$$,则打印$$$-1$$$。
示例
输入复制
41146 6 12 12324 120 21042 4 6 10
输出复制
2553
注意
在第一个测试用例中,$$$\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$$$。