CF1593D2.Half of Same

This problem is a complicated version of D1, but it has significant differences, so read the whole statement.

Polycarp has an array of $n$ ($n$ is even) integers $a_1, a_2, \dots, a_n$. Polycarp conceived of a positive integer $k$. After that, Polycarp began performing the following operations on the array: take an index $i$ ($1 \le i \le n$) and reduce the number $a_i$ by $k$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that at least half of the numbers in the array became the same. Find the maximum $k$ at which such a situation is possible, or print $-1$ if such a number can be arbitrarily large.

本题是 D1 的复杂版本，但存在显著差异，因此请完整阅读题面。

Polycarp 有一个长度为 $n$（$n$ 为偶数）的整数数组 $a_1, a_2, \dots, a_n$。Polycarp 构思了一个正整数 $k$。随后，Polycarp 开始对数组执行如下操作：选取一个下标 $i$（$1 \le i \le n$），并将 $a_i$ 减少 $k$。

在 Polycarp 执行了若干次（可能为零次）此类操作后，发现数组中至少有一半的数变得相同。请找出满足该情况的最大 $k$；若这样的 $k$ 可以任意大，则输出 $-1$。

The first line contains one integer $t$ ($1 \le t \le 10$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of two lines. The first line contains an even integer $n$ ($4 \le n \le 40$) ($n$ is even). The second line contains $n$ integers $a_1, a_2, \dots a_n$ ($-10^6 \le a_i \le 10^6$).

It is guaranteed that the sum of all $n$ specified in the given test cases does not exceed $100$.

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

每个测试用例由两行组成。第一行包含一个偶数 $n$（$4 \le n \le 40$）（即 $n$ 为偶数）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^6 \le a_i \le 10^6$）。

保证所有测试用例中给定的 $n$ 值之和不超过 $100$。

For each test case output on a separate line an integer $k$ ($k \ge 1$) — the maximum possible number that Polycarp used in operations on the array, or $-1$, if such a number can be arbitrarily large.

对于每个测试用例，在单独的一行上输出一个整数 $k$（$k \ge 1$）——即 Polycarp 在数组上执行操作时所能使用的最大可能的数；若这样的数可以任意大，则输出 $-1$。