你正在玩一款名为 Mathcraft 的沙盒游戏。每个等级为 $k$ 的合成表可以产出通过将两个介于 $1$ 和 $k$ 之间的数相乘得到的所有可能乘积。

如果你将第 $k$ 个合成表展开，你会得到数组 $[1\cdot 1, 1\cdot 2, \dots, 1\cdot k, 2\cdot 1, 2\cdot 2, \dots, 2\cdot k, \dots, k\cdot 1, k\cdot 2, \dots, k\cdot k]$。

例如，对于 $k = 4$，展开后的表为 $[1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16]$。

你的朋友 Bob 制作了某个展开后合成表的一个（连续）子数组。这个子数组为 $a_1, a_2, \dots, a_n$。

你想知道 Bob 的技术有多好，所以你想找到他的合成表的最小可能等级。具体来说，你想确定最小的 $k$，使得 $a_1, a_2, \dots, a_n$ 作为第 $k$ 个展开表的子数组出现。

如果一个数组 $b$ 可以通过从数组 $c$ 的开头删除若干个（可能为零个或全部）元素以及从末尾删除若干个（可能为零个或全部）元素来获得，则称数组 $b$ 是数组 $c$ 的子数组。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 500$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 100$) —— 数组 $a_1, a_2, \dots, a_n$ 的长度。

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

注意，所有测试用例中 $n$ 的总和没有限制。

输出格式

对于每个测试用例，输出单行，包含一个整数：最小的合成表等级 $k$，使得数组 $a_1, a_2, \dots, a_n$ 作为第 $k$ 个展开表的连续子数组出现。对于给定的输入，这样的 $k$ 总是存在。

样例

输入 1

4
4
4 6 8 10
6
8 3 6 9 12 4
5
30 40 50 60 70
4
1 2 2 4

输出 1

5
4
10
2

说明

样例 1 说明：在第一个测试用例中，数组 $[4, 6, 8, 10]$ 是第 $5$ 个展开表的子数组，该表为 $[1, 2, 3, 4, 5, 2, 4, 6, 8, 10, \dots, 5, 10, 15, 20, 25]$。不存在更小的合法 $k$，因此答案为 $5$。

在第二个测试用例中，数组 $[8, 3, 6, 9, 12, 4]$ 是第 $4$ 个展开表的子数组，该表为 $[1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16]$。