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.

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.