Neat Array 2

Problem Description

Polycarp has an array $a_1, a_2, \dots, a_n$ of length $n$ (where $n$ is even). Polycarp is also given a positive integer $k$, and he starts performing the following operation on $a$: choose an index $i$ ($1 \le i \le n$) and subtract $k$ from $a_i$.

After Polycarp performs some number of operations (possibly zero), at least half of the elements in $a$ become equal. Find the largest valid $k$; if $k$ can be arbitrarily large, output $-1$.

Input Format

The first line contains an integer $t$, the number of test cases.

Each test case then has two lines. The first contains an even integer $n$. The second contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

For each test case, output a single integer $k$ ($k \ge 1$) on its own line — the largest number Polycarp can use to perform operations on the array — or $-1$ if $k$ can be arbitrarily large.

Sample Input

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

Sample Output

13
2
-1
-1

Constraints

For all data, $1 \le t \le 10$, $4 \le n \le 40$ (with $n$ even), $-10^6 \le a_i \le 10^6$, and the sum of all $n$ does not exceed $100$.