问题描述

爱丽丝有一个数组 $a$ ，由 $n$ 个正整数组成。数组满足一个美丽的性质，即对于每个 $1 \leq i \leq n - 1$ ，都有 $a_i \mid a_{i+1}$ ( $a_i$ 能整除 $a_{i+1}$ )。

鲍勃看到爱丽丝的数组很漂亮，心生嫉妒。为了破坏她，鲍勃首先创建了一个大小为 $n$ 的数组 $b$ ，使得每个 $1 \leq i \leq n$ 都有 $b_i=a_i$ 。然后，他选择一个正整数 $x$ 并将 $b$ 中的某些元素(可能没有，也可能全部)乘以 $x$ 。

从形式上看，他选择了一个(可能为空)子集 $S\subseteq \{1,2,\ldots,n\}$ ，并为每个 $i\in S$ 设置了 $b_i=b_i\cdot x$ 。

给你一个数组 $b$ ，但你不知道数组 $a$ 和所选的数 $x$ 。请输出鲍勃可能选择的任何整数 $x$ ，以便将正确数组 $a$ 的某个元素子集与 $x$ 相乘，得到数组 $b$ 。可以保证答案是存在的。如果有多个可能的整数，则可以输出其中任何一个。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 2\cdot10^5$ )。测试用例说明如下。

每个测试用例的第一行都包含一个整数 $n$ ( $2 \leq n \leq 6\cdot10^5$ ) - 数组的长度 $b$ 。

每个测试用例的第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$ ( $1 \leq b_i \leq 10^9$ ) - 表示数组 $b$ 。

可以保证数组 $b$ 可以从语句中描述的某个漂亮数组 $a$ 和某个正整数 $x$ 中得到。

保证所有测试用例中 $n$ 的总和不超过 $6\cdot 10^5$ 。

输出格式

对于每个测试用例，在新行中输出 $x$ ( $1 \leq x \leq 10^9$ ) 的任何可能值。( $1 \leq x \leq 10^9$ ) 的任何可能值。保证至少存在一个 $x$ 值。

样例输入

4
2
2 4
3
1 1000000000 500000000
4
4 8 4 8
7
42 42 14 84 28 73080 255780

样例输出

343
2
4
6

说明

在第一个测试案例中，鲍勃可能选择了 $x=343$ 和 $S=\{\}$ (这意味着他根本没有更改数组 $a$ )。

在第三个测试案例中，鲍勃可能选择了 $x=4$ 和 $S=\{1,2\}$ ，这意味着他将 $b_1$ 和 $b_2$ 乘以 $4$ 。原始数组为 $\{1,2,4,8\}$ ，满足所需的属性。