您有一个由 $$$n$$$ 个非负整数组成的数组 $$$a$$$。让我们为某个正整数 $$$x$$$ 定义 $$$f(a, x) = [a_1 \bmod x, a_2 \bmod x, \dots, a_n \bmod x]$$$。找到最大的 $$$x$$$,使得 $$$f(a, x)$$$ 是回文。
这里, $$$a \bmod x$$$ 是 $$$a$$$ 除以 $$$x$$$ 的整数除法的余数。
如果向后读取的数组与向前读取的数组相同,则该数组是回文数组。更正式地说,如果对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$) $$$a_i = a_{n - i + 1}$$$,则长度为 $$$n$$$ 的数组 $$$a$$$ 是回文。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$)。
保证所有$$$n$$$的总和不超过$$$10^5$$$。
输出
对于每个测试用例输出最大的 $$$x$$$,使得 $$$f(a, x)$$$ 是回文。如果$$$x$$$可以无限大,则输出$$$0$$$。
示例
输入 #1
4 2 1 2 8 3 0 1 2 0 3 2 1 1 0 3 100 1 1000000000
输出 #1
1 2 0 999999900
注意
在第一个示例中,$$$f(a, x = 1) = [0, 0]$$$ 是一个回文。
在第二个示例中, $$$f(a, x = 2) = [1, 0, 1, 0, 0, 1, 0, 1]$$$ 是一个回文。
可以证明,在前两个例子中,没有更大的$$$x$$$满足条件。
在第三个例子中,对于任何$$$x$$$,$$$f(a, x) = [0]$$$,所以我们可以选择它无限大,所以答案是$$$0$$$。