B. Сделать почти равными по модулю
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
xi - Solar Storm
⠀

Вам дан массив различных целых положительных чисел $$$a_1, a_2, \dots, a_n$$$. Вы должны выполнить следующую операцию ровно один раз:

  • выбрать целое положительное число $$$k$$$;
  • для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ заменить $$$a_i$$$ на $$$a_i \text{ mod } k^\dagger$$$.

Найдите такое значение $$$k$$$, такое что $$$1 \leq k \leq 10^{18}$$$, чтобы массив $$$a_1, a_2, \dots, a_n$$$ содержал ровно $$$2$$$ различных значения после применения операции. Можно показать, что при ограничениях задачи хотя бы одно такое $$$k$$$ всегда существует. Если существует несколько решений, выведите любое из них.

$$$^\dagger$$$ $$$a \text{ mod } b$$$ обозначает остаток от деления $$$a$$$ на $$$b$$$. Например:

  • $$$7 \text{ mod } 3=1$$$, так как $$$7 = 3 \cdot 2 + 1$$$
  • $$$15 \text{ mod } 4=3$$$, так как $$$15 = 4 \cdot 3 + 3$$$
  • $$$21 \text{ mod } 1=0$$$, так как $$$21 = 21 \cdot 1 + 0$$$
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{17}$$$) — начальные числа в массиве. Гарантируется, что все $$$a_i$$$ различны.

Обратите внимание, что нет никаких ограничений на сумму $$$n$$$ по всем наборам входных данных.

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

Для каждого набора входных данных выведите одно целое число: значение $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$) такое, что массив $$$a_1, a_2, \dots, a_n$$$ будет содержать ровно $$$2$$$ различных значения после применения операции.

Пример
Входные данные
5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1
Выходные данные
7
30
3
5000
1000000000000000000
Примечание

В первом наборе входных данных можно выбрать $$$k = 7$$$. Массив станет равным $$$[8 \text{ mod } 7, 15 \text{ mod } 7, 22 \text{ mod } 7, 30 \text{ mod } 7] = [1, 1, 1, 2]$$$ и будет содержать ровно $$$2$$$ различных значения ($$$\{1, 2\}$$$).

Во втором наборе входных данных можно выбрать $$$k = 30$$$. Массив станет равным $$$[0, 0, 8, 0, 8]$$$, то есть будет содержать ровно $$$2$$$ различных значения ($$$\{0, 8\}$$$). Заметим, что выбор $$$k = 10$$$ также будет корректным решением.

В последнем наборе входных данных можно выбрать $$$k = 10^{18}$$$. Массив станет равным $$$[2, 1]$$$ и будет содержать ровно $$$2$$$ различных значения ($$$\{1, 2\}$$$). Заметим, что выбор $$$k = 10^{18} + 1$$$ не будет корректным, так как должно выполняться $$$1 \leq k \leq 10^{18}$$$.