D. Еще одна задача с массивами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны целое число $$$n$$$ и массив $$$a$$$ длины $$$n$$$.

Найдите наименьшее целое $$$x$$$ ($$$2 \le x \le 10^{18}$$$), такое что существует индекс $$$i$$$ ($$$1 \le i \le n$$$) с $$$\gcd$$$$$$^{\text{∗}}$$$$$$(a_i, x) = 1$$$. Если такого $$$x$$$ в диапазоне $$$[2,10^{18}]$$$ нет, выведите $$$-1$$$.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

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

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

Каждый из следующих $$$t$$$ наборов входных данных состоит из двух строк:

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел, разделённых пробелами: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).

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

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

Для каждого набора входных данных выведите одно целое число: наименьшее $$$x$$$ ($$$2 \le x \le 10^{18}$$$), для которого существует индекс $$$i$$$ с $$$\gcd(a_i, x) = 1$$$. Если такого $$$x$$$ нет в диапазоне $$$[2,10^{18}]$$$, выведите $$$-1$$$.

Пример
Входные данные
4
1
1
4
6 6 12 12
3
24 120 210
4
2 4 6 10
Выходные данные
2
5
5
3
Примечание

В первом наборе входных данных, $$$\gcd(2,1)=1$$$, что является наименьшим числом, удовлетворяющим условию.

Во втором наборе входных данных:

  • $$$\gcd(2,6)=2$$$, $$$\gcd(2,12)=2$$$, так что $$$2$$$ не может быть ответом,
  • $$$\gcd(3,6)=3$$$, $$$\gcd(3,12)=3$$$, так что $$$3$$$ не может быть ответом,
  • $$$\gcd(4,6)=2$$$, $$$\gcd(4,12)=4$$$, так что $$$4$$$ не может быть ответом,
  • $$$\gcd(5,6)=1$$$, так что ответ $$$5$$$.

В третьем наборе входных данных:

  • $$$\gcd(2,24)=2$$$, $$$\gcd(2,120)=2$$$, $$$\gcd(2,210)=2$$$, так что $$$2$$$ не может быть ответом,
  • $$$\gcd(3,24)=3$$$, $$$\gcd(3,120)=3$$$, $$$\gcd(3,210)=3$$$, так что $$$3$$$ не может быть ответом,
  • $$$\gcd(4,24)=4$$$, $$$\gcd(4,120)=4$$$, $$$\gcd(4,210)=2$$$, так что $$$4$$$ не может быть ответом.
  • $$$\gcd(5,24)=1$$$, так что ответ $$$5$$$.

В четвертом наборе входных данных:

  • $$$\gcd(2,2)=2$$$, $$$\gcd(2,4)=2$$$, $$$\gcd(2,6)=2$$$, $$$\gcd(2,10)=2$$$, так что $$$2$$$ не может быть ответом,
  • $$$\gcd(3,2)=1$$$, так что ответ $$$3$$$.