对于两个整数 $$$x$$$ 和 $$$y$$$ ($$$x,y\ge 2$$$),我们会说 $$$x$$$ 是 $$$y$$$ 的生成器,当且仅当 $$$x$$$ 可以通过执行以下操作一定次数(可能为零)来转换为 $$$y$$$:
- 选择 $$$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 给你一个数组 $$$a$$$,由 $$$n$$$ 成对不同的整数组成 ($$$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,\ldots,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$$$。
在第二个测试用例中,可以证明不可能找到四个整数的公共生成器。