A14611 | 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.

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$ .

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.