D2. Половина одинаковых
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача является усложнённой версией задачи D1, но при этом имеет существенные отличия, поэтому прочитайте условие полностью.

У Поликарпа есть массив из $$$n$$$ ($$$n$$$ — чётное число) целых чисел $$$a_1, a_2, \dots, a_n$$$. Поликарп задумал положительное целое число $$$k$$$. После этого Поликарп стал совершать над массивом операции следующего вида: взять произвольный индекс $$$i$$$ ($$$1 \le i \le n$$$) и уменьшить число $$$a_i$$$ на $$$k$$$.

После того, как Поликарп совершил некоторое (возможно, нулевое) количество таких операций, оказалось, что не менее половины чисел в массиве стали одинаковыми. Найдите максимальное $$$k$$$, при котором такая ситуация возможна, или выведите $$$-1$$$, если такое число может быть сколь угодно большим.

Входные данные

В первой строке записано одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите одно целое число $$$k$$$ ($$$k \ge 1$$$) — максимальное возможное число, которое Поликарп использовал в операциях над массивом, или $$$-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
Выходные данные
13
2
-1
-1