题目背景

Special for beginners, ^_^

题目描述

在一个魔法世界里，你是一个炼金术师，面前有 n 个怪兽，每个怪兽有一个力量值 aᵢ（整数）。你手里有一种魔法药水，它的魔力值为 x（整数）。当你把药水投给怪兽 i 时，只有当 gcd(aᵢ, x) = 1 时，药水才能完全生效（也就是怪兽会被“净化”）。

现在你的任务是找到最小的魔力值 x（范围 2 ≤ x ≤ 10¹⁸），使得每个怪兽能被药水净化。如果找不到这样的 x，输出 -1。

输入格式

第一行包含整数 t（1 ≤ t ≤ 10⁴），表示测试用例数量。

接下来每个测试用例包含两行：

第一行：整数 n（1 ≤ n ≤ 10⁵），怪兽的数量。

第二行：n 个整数 a₁, a₂, …, aₙ（1 ≤ aᵢ ≤ 10¹⁸），表示每个怪兽的力量值。

保证所有测试用例中 n 的总和不超过 10⁵。

输出格式

一个整数, 表示 A 和 B 的和.

样例

4
1
1
4
6 6 12 12
3
24 120 210
4
2 4 6 10

2
5
5
3

样例解释

第一个怪兽力量是 1，gcd(2,1)=1，所以答案是 2。

第二组怪兽力量都是 6 和 12，2、3、4 都不能净化任何怪兽，但 5 可以，答案是 5。

第三组怪兽力量 24、120、210，最小能净化的魔力值是 5。

第四组怪兽力量 2、4、6、10，最小能净化的魔力值是 3。

出题人（李昱廷）