Alice 有一个数组 $$$a$$$,由 $$$n$$$ 正整数组成。该数组满足 $$$a_i$$$ 除以 $$$a_{i+1}$$$ 对于每个 $$$1 \leq i \leq n - 1$$$ 的美丽属性。
鲍勃看到爱丽丝美丽的阵列,很嫉妒。为了破坏她,Bob 首先创建一个大小为 $$$n$$$ 的数组 $$$b$$$,使得每个 $$$1 \leq i \leq n$$$ 都有 $$$b_i=a_i$$$。然后,他选择一个正整数 $$$x$$$ 并将 $$$b$$$ 中的一些(可能没有,也可能全部)元素乘以 $$$x$$$。
正式地,他选择一个(可能为空)子集 $$$S\subseteq\{1,2,\ldots,n\}$$$,并且对于 S$$$ 中的每个 $$$i\,他设置 $$$b_i:=b_i\cdot x$$$。
给定一个数组 $$$b$$$,但你不知道数组 $$$a$$$ 和所选数字 $$$x$$$。请输出 Bob 可以选择的任何整数 $$$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$$$) 的任何可能值。保证 $$$x$$$ 至少存在一个值。
示例
输入复制
422 431 1000000000 50000000044 8 4 8742 42 14 84 28 73080 255780
输出复制
343 2 4 6
注意
在第一个测试用例中,Bob 可能选择 $$$x=343$$$ 和 $$$S=\{\}$$$ (意味着他根本没有更改数组 $$$a$$$)。
在第三个测试用例中,Bob 可能选择 $$$x=4$$$ 和 $$$S=\{1,2\}$$$,这意味着他将 $$$b_1$$$ 和 $$$b_2$$$ 都乘以 $$$4$$$。原数组为$$$\{1,2,4,8\}$$$,满足要求的属性。