题目描述

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

请找到最小的整数 $x$，满足：

2 <= x <= 10^18

并且数组中存在某个元素 $a_i$，使得：

gcd(a_i, x) = 1

如果不存在这样的 $x$，输出 -1。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据包含两行：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

保证所有测试数据的 $n$ 之和不超过 $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

样例说明

第一组测试数据中，$\gcd(1,2)=1$，且 $2$ 是允许范围内最小的数，所以答案为 $2$。

第二组测试数据中，$2,3,4$ 都会和数组中所有数有大于 $1$ 的公因数；而 $\gcd(6,5)=1$，所以答案为 $5$。

第三组测试数据中，$2,3,4$ 也都不满足条件；而 $\gcd(24,5)=1$，所以答案为 $5$。

第四组测试数据中，$2$ 与所有数组元素都有公因数 $2$，但 $\gcd(2,3)=1$，所以答案为 $3$。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 10^5$
• $1 \le a_i \le 10^{18}$
• 所有测试数据的 $n$ 之和不超过 $10^5$

来源

Codeforces Round 1062 (Div. 4), Problem D - Yet Another Array Problem