Busy Beaver 刚刚在小学里学习了约数和倍数。现在，Busy Beaver 用以下问题向你发起挑战。

给你一个长度为 $N$ 的序列 $a$。请找到任意一个正整数 $X$，满足：

• 对于每个 $i$，$X$ 要么是 $a_i$ 的倍数，要么是 $a_i$ 的约数；
• 存在至少一个下标 $i$，使得 $X$ 是 $a_i$ 的倍数；
• 存在至少一个下标 $i$，使得 $X$ 是 $a_i$ 的约数；

或者确定不存在这样的整数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含一个整数 $N$ ($2 \le N \le 3 \cdot 10^5$) —— 序列 $a$ 的长度。

每个测试用例的第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^9$)。

所有测试用例中 $N$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— $X$ 的值，如果不存在这样的 $X$，则输出 $-1$。

如果有多个满足条件的 $X$ 值，你可以输出其中任意一个。

子任务

本题共有两个子任务。

• （40 分）：所有测试用例中 $N$ 的总和不超过 2000。
• （60 分）：无附加限制。

样例

输入样例 1

6
3
36 2 12
6
10 20 30 40 50 60
7
8 7 6 5 4 3 2
6
10 6 1 90 2 15
3
10 2 5
2
1 1

输出样例 1

6
10
-1
30
10
1

说明

在第一个测试用例中，$6$ 是 $36$ 和 $12$ 的约数，且是 $2$ 的倍数。

在第二个测试用例中，$10$ 是所有元素的约数，且是 $10$ 的倍数。

在第三个测试用例中，不存在满足限制条件的整数。