CFCF2167D.Yet Another Array Problem

给定一个整数 $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$。