题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。你可以对该数组执行以下操作任意次（包括 $0$ 次）：

• 选择一个整数 $k \ge 1$，使得 $2k+1 \le m$（其中 $m$ 是当前数组的长度）。
• 在当前数组中选择 $2k+1$ 个严格递增的下标 $i_1 < i_2 < \dots < i_{2k+1}$（即 $1 \le i_1 < i_2 < \dots < i_{2k+1} \le m$）。
• 将数组中下标为 $i_{k+1}$ 的元素删除（换言之，删除你所选出的这 $2k+1$ 个元素中处于正中间位置的那一个）。

每次操作后，数组的长度会减 $1$，剩余的元素会按原有的相对顺序拼接在一起形成新的数组。

假设在执行完所有操作后，最终剩余的数组为 $b_1, b_2, \dots, b_m$。请问 $\gcd(b_1, b_2, \dots, b_m)$（即剩余数组所有元素的最大公约数）可能的最大值是多少？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 100$）—— 表示数组 $a$ 的初始长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组 $a$ 的初始元素。

输出格式

对于每个测试用例，输出一行一个整数，表示能够达到的最大可能的 $\gcd$ 值。

样例输入 1

4
7
2 4 6 7 8 9 10
2
55 55555
4
1000000 1000 1 1000000000
5
23 32 23 32 23

样例输出 1

2
5
1000000
23

说明

样例解释

在第一个测试用例中，给定的初始数组为 $[2, 4, 6, 7, 8, 9, 10]$。

• 我们可以选择 $k=2$，并挑出下标序列 $[1, 3, 4, 6, 7]$。在这个序列中，位于中间（第 $k+1 = 3$ 个）的下标是 $4$。因此，我们删除第 $4$ 个元素 $a_4 = 7$。数组变为 $[2, 4, 6, 8, 9, 10]$。
• 接着，我们可以选择 $k=1$，并挑出下标序列 $[2, 5, 6]$。在这个序列中，位于中间的下标是 $5$。因此，我们删除第 $5$ 个元素（值为 $9$）。数组变为 $[2, 4, 6, 8, 10]$。

最终数组的所有元素的最大公约数为 $2$。可以证明无法得到比 $2$ 更大的答案。

数据范围

• 对于所有测试点，保证 $1 \le t \le 500$。
• 对于每个测试用例，保证 $1 \le n \le 100$。
• 对于每个测试用例，保证 $1 \le a_i \le 10^9$。
• 保证所有的输入数值均为整数。