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

Вам дан массив $$$a$$$ длины $$$n$$$. Назовем целое положительное число $$$x$$$ хорошим, если нельзя найти такой подотрезок$$$^{\dagger}$$$ массива, что наименьшее общее кратное всех элементов на нём равно $$$x$$$.

Вам требуется найти наименьшее хорошее число.

Подотрезком $$$^{\dagger}$$$ массива $$$a$$$ называется набор элементов $$$a_l, a_{l + 1}, \ldots, a_r$$$ для некоторых $$$1 \le l \le r \le n$$$. Будем обозначать такой подотрезок $$$[l, r]$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.

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

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

Для каждого набора входных выведите единственное целое число — наименьшее хорошее число.

Пример
Входные данные
6
3
1 2 3
5
1 2 3 4 5
2
2 3
1
1000000000
12
1 8 4 2 3 5 7 2 9 10 11 13
12
7 2 5 4 2 1 1 2 3 11 8 9
Выходные данные
4
7
1
1
16
13
Примечание

В первом наборе входных данных, $$$4$$$ — хорошее число, при этом оно является наименьшим, так как числа $$$1,2,3$$$ встречаются в массиве, а значит, есть подотрезки массива длины $$$1$$$ с наименьшими общими кратными $$$1,2,3$$$. При этом нельзя найти подотрезок массива с наименьшим общим кратным равным $$$4$$$.

Во втором наборе входных данных, $$$7$$$ — хорошее число. При этом числа $$$1,2,3,4,5$$$ встречаются в массиве явно, а число $$$6$$$ является наименьшим общим кратных подотрезков $$$[2, 3]$$$ и $$$[1, 3]$$$.

В третьем наборе входных данных, $$$1$$$ — хорошее число, так как наименьшие общие кратные для чисел на отрезках $$$[1, 1], [1, 2], [2, 2]$$$, соответственно, равны $$$2,6,3$$$.