对于两个整数 $x$ 和 $y$ ($x, y \ge 2$)，如果 $x$ 可以通过执行若干次（可能为零次）以下操作转化为 $y$，则称 $x$ 是 $y$ 的生成元（generator）：

• 选择 $x$ 的一个约数 $d$ ($d \ge 2$)，然后将 $x$ 增加 $d$。

例如：

• $3$ 是 $8$ 的生成元，因为我们可以执行以下操作：$3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$；
• $4$ 是 $10$ 的生成元，因为我们可以执行以下操作：$4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$；
• $5$ 不是 $6$ 的生成元，因为我们无法通过上述操作将 $5$ 转化为 $6$。

现在，Kevin 给你一个包含 $n$ 个两两不同的整数的数组 $a$ ($a_i \ge 2$)。你需要找到一个整数 $x \ge 2$，使得对于每个 $1 \le i \le n$，$x$ 都是 $a_i$ 的生成元，或者确定这样的整数不存在。

输入格式

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$) —— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 4 \cdot 10^5$) —— 数组 $a$ 的元素。保证元素两两不同。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数 $x$ —— 你找到的整数。如果不存在合法的 $x$，则输出 $-1$。

如果有多个答案，你可以输出其中任意一个。

样例

输入格式 1

4
3
8 9 10
4
2 3 4 5
2
147 154
5
3 6 8 25 100000

输出格式 1

2
-1
7
3

说明

在第一个测试用例中，对于 $x = 2$：

• $2$ 是 $8$ 的生成元，因为我们可以执行以下操作：$2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$；
• $2$ 是 $9$ 的生成元，因为我们可以执行以下操作：$2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$；
• $2$ 是 $10$ 的生成元，因为我们可以执行以下操作：$2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$。

在第二个测试用例中，可以证明不存在这四个整数的公共生成元。