题目描述

给定一个整数 $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$ 的最大公约数。

输入格式

第一行包含一个整数 $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$。

说明/提示

在第一个测试用例中，$\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$。

由 ChatGPT 5 翻译

样例

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

2
5
5
3