У Алисы есть массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел. Массив обладает красивым свойством, что $$$a_i$$$ является делителем $$$a_{i+1}$$$ для каждого $$$1 \leq i \leq n - 1$$$.
Боб видит красивый массив Алисы и завидует. Чтобы подорвать её успех, Боб сначала создает массив $$$b$$$ размером $$$n$$$, такой что $$$b_i=a_i$$$ для каждого $$$1 \leq i \leq n$$$. Затем он выбирает положительное целое число $$$x$$$ и умножает некоторые (возможно, ни один или все) элементы в $$$b$$$ на $$$x$$$.
Формально, он выбирает (возможно, пустое) подмножество $$$S\subseteq\{1,2,\ldots,n\}$$$, и для каждого $$$i\in S$$$ он присваивает $$$b_i:=b_i\cdot x$$$.
Вам дан массив $$$b$$$, но вы не знаете массив $$$a$$$ и выбранное число $$$x$$$. Пожалуйста, выведите любое целое число $$$x$$$, которое Боб мог выбрать, чтобы в результате умножения какого-то подмножества элементов корректного массива $$$a$$$ на $$$x$$$ он получил массив $$$b$$$. Гарантируется, что ответ существует. Если существует несколько решений, выведите любое из них.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 6\cdot10^5$$$) — длина массива $$$b$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — массив $$$b$$$.
Гарантируется, что массив $$$b$$$ может быть получен из некоторого красивого массива $$$a$$$ и некоторого положительного целого числа $$$x$$$ как описано в условии.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$6\cdot 10^5$$$.
Для каждого набора входных данных выведите любое возможное значение $$$x$$$ ($$$1 \leq x \leq 10^9$$$) на отдельной строке. Гарантируется, что существует хотя бы одно значение $$$x$$$.
422 431 1000000000 50000000044 8 4 8742 42 14 84 28 73080 255780
343 2 4 6
В первом наборе входных данных возможно, что Боб выбрал $$$x=343$$$ и $$$S=\{\}$$$ (что означает, что он вообще не изменил массив $$$a$$$).
В третьем наборе входных данных возможно, что Боб выбрал $$$x=4$$$ и $$$S=\{1,2\}$$$, что означает, что он умножил $$$b_1$$$ и $$$b_2$$$ на $$$4$$$. Исходный массив был $$$\{1,2,4,8\}$$$, что удовлетворяет требуемому свойству.
