O. 至少一半要相等
time limit per test
0.75 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

现在有一个长度为 $$$n$$$($$$n$$$为偶数) 的序列，该序列中数字互不相同，你需要选择一个正整数 $$$k$$$，然后对序列中任意一个数字 $$$a_i$$$ 执行任意次如下操作：

$$$$$$ a_i=a_i-k $$$$$$

在一定次数的该操作后，你需要使序列中至少一半的数字相等，请问 $$$k$$$ 的最大值是多少，如果 $$$k$$$ 可以无限大，则输出 $$$0$$$。

Input

第一行，一个整数 $$$t(1\le t \le 100)$$$。

对于每组数据：

第一行，一个整数 $$$n(2\le n \le 5000)$$$，$$$n$$$ 是一个偶数，代表序列长度。 接下来一行，一个长度为 $$$n$$$ 的序列 $$$a$$$，该序列中数字互不相同，其中的每个数字 $$$1\le a_i \le 10^6$$$。

保证在同一测试点内的 $$$\sum n \le 5000$$$。

Output

对于每组数据，输出一行代表可行的 $$$k$$$ 的最大值，如果 $$$k$$$ 可以无限大，则输出 $$$0$$$。

Example
Input
3
6
1 2 3 4 5 6
2
1 10
8
1 5 4 9 8 13 12 11
Output
2
0
4