#P1593D2. Half of Same

Half of Same

Description

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

Polycarp has an array of nn (nn is even) integers a1,a2,,ana_1, a_2, \dots, a_n. Polycarp conceived of a positive integer kk. After that, Polycarp began performing the following operations on the array: take an index ii (1in1 \le i \le n) and reduce the number aia_i by kk.

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 kk at which such a situation is possible, or print 1-1 if such a number can be arbitrarily large.

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

Each test case consists of two lines. The first line contains an even integer nn (4n404 \le n \le 40) (nn is even). The second line contains nn integers a1,a2,ana_1, a_2, \dots a_n (106ai106-10^6 \le a_i \le 10^6).

It is guaranteed that the sum of all nn specified in the given test cases does not exceed 100100.

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

Input

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

Each test case consists of two lines. The first line contains an even integer nn (4n404 \le n \le 40) (nn is even). The second line contains nn integers a1,a2,ana_1, a_2, \dots a_n (106ai106-10^6 \le a_i \le 10^6).

It is guaranteed that the sum of all nn specified in the given test cases does not exceed 100100.

Output

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

Samples

样例输入 1

4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1

样例输出 1

13
2
-1
-1