CF2167D.Yet Another Array Problem

You are given an integer $n$ and an array $a$ of length $n$.

Find the smallest integer $x$ ($2 \le x \le 10^{18}$) such that there exists an index $i$ ($1 \le i \le n$) with $\gcd$$^{\text{∗}}$$(a_i, x) = 1$. If no such $x$ exists within the range $[2,10^{18}]$, output $-1$.

$^{\text{∗}}$$\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

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

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each of the following $t$ test cases consists of two lines:

The first line contains a single integer $n$ ($1 \le n \le 10^{5}$) — the length of the array.

The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$).

It is guaranteed that the total sum of $n$ across all test cases does not exceed $10^{5}$.

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

For each test case, output a single integer: the smallest $x$ ($2 \le x \le 10^{18}$) such that there exists an index $i$ with $\gcd(a_i, x) = 1$. If there is no such $x$ in the range $[2,10^{18}]$, print $-1$.

对于每个测试用例，输出一个整数：满足存在某个下标 $i$ 使得 $\gcd(a_i, x) = 1$ 的最小 $x$（其中 $2 \le x \le 10^{18}$）。若在区间 $[2,10^{18}]$ 内不存在这样的 $x$，则输出 $-1$。

In the first test case, $\gcd(2,1)=1$, which is the smallest number satisfying the condition.

In the second test case:

• $\gcd(2,6)=2$, $\gcd(2,12)=2$, so $2$ cannot be the answer.
• $\gcd(3,6)=3$, $\gcd(3,12)=3$, so $3$ cannot be the answer.
• $\gcd(4,6)=2$, $\gcd(4,12)=4$, so $4$ cannot be the answer.
• $\gcd(5,6)=1$, so the answer is $5$.

In the third test case:

• $\gcd(2,24)=2$, $\gcd(2,120)=2$, $\gcd(2,210)=2$, so $2$ cannot be the answer.
• $\gcd(3,24)=3$, $\gcd(3,120)=3$, $\gcd(3,210)=3$, so $3$ cannot be the answer.
• $\gcd(4,24)=4$, $\gcd(4,120)=4$, $\gcd(4,210)=2$, so $4$ cannot be the answer.
• $\gcd(5,24)=1$, so the answer is $5$.

In the fourth test case:

• $\gcd(2,2)=2$, $\gcd(2,4)=2$, $\gcd(2,6)=2$, $\gcd(2,10)=2$, so $2$ cannot be the answer.
• $\gcd(3,2)=1$, so the answer is $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$。