E. Общий генератор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для двух целых чисел $$$x$$$ и $$$y$$$ ($$$x,y\ge 2$$$) назовём $$$x$$$ генератором $$$y$$$, если и только если $$$x$$$ может быть преобразован в $$$y$$$, выполняя следующую операцию некоторое количество раз (возможно, ноль):

  • Выберите делитель $$$d$$$ ($$$d\ge 2$$$) числа $$$x$$$, затем увеличьте $$$x$$$ на $$$d$$$.

Например:

  • $$$3$$$ является генератором $$$8$$$, так как мы можем выполнить следующие операции: $$$3 \xrightarrow{d = 3} 6 \xrightarrow{d = 2} 8$$$;
  • $$$4$$$ является генератором $$$10$$$, так как мы можем выполнить следующие операции: $$$4 \xrightarrow{d = 4} 8 \xrightarrow{d = 2} 10$$$;
  • $$$5$$$ не является генератором $$$6$$$, так как мы не можем преобразовать $$$5$$$ в $$$6$$$ с помощью вышеуказанной операции.

Теперь Кевин даст вам массив $$$a$$$, состоящий из $$$n$$$ попарно различных целых чисел ($$$a_i\ge 2$$$).

Вам нужно найти целое число $$$x\ge 2$$$ такое, что для каждого $$$1\le i\le n$$$, $$$x$$$ является генератором $$$a_i$$$, или определить, что такое число не существует.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$2\le a_i\le 4\cdot 10^5$$$) — элементы массива $$$a$$$. Гарантируется, что элементы попарно различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число $$$x$$$ — найденное вами целое число. Выведите $$$-1$$$, если не существует подходящего $$$x$$$.

Если существует несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
4
3
8 9 10
4
2 3 4 5
2
147 154
5
3 6 8 25 100000
Выходные данные
2
-1
7
3
Примечание

В первом наборе входных данных, для $$$x=2$$$:

  • $$$2$$$ является генератором $$$8$$$, так как мы можем выполнить следующие операции: $$$2 \xrightarrow{d = 2} 4 \xrightarrow{d = 4} 8$$$;
  • $$$2$$$ является генератором $$$9$$$, так как мы можем выполнить следующие операции: $$$2 \xrightarrow{d = 2} 4 \xrightarrow{d = 2} 6 \xrightarrow{d = 3} 9$$$.
  • $$$2$$$ является генератором $$$10$$$, так как мы можем выполнить следующие операции: $$$2 \xrightarrow{d = 2} 4 \xrightarrow{d = 2} 6 \xrightarrow{d = 2} 8 \xrightarrow{d = 2} 10$$$.

Во втором наборе входных данных можно доказать, что невозможно найти общий генератор данных четырёх целых чисел.