A. Нечётный ластик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a_1, a_2, \ldots, a_n$$$. К нему можно применить следующую операцию произвольное количество раз (возможно, ни одного):

  • Выберите целое число $$$k \geq 1$$$ такое, что $$$2k+1 \le m$$$, и $$$2k+1$$$ индексов $$$i_1, i_2, \ldots, i_{2k+1}$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_{2k+1} \le m$$$), где $$$m$$$ — текущая длина массива. Затем удалите $$$i_{k+1}$$$-й элемент из массива.
Заметим, что после каждой операции длина массива уменьшается на один, а оставшиеся части массива соединяются.

Пусть $$$b_1, b_2, \ldots, b_m$$$ — массив, оставшийся после всех операций.

Каково максимально возможное значение $$$\gcd(b_1, b_2, \ldots, b_m)$$$, где $$$\gcd$$$ массива чисел обозначает их наибольший общий делитель (НОД)?

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

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

В первой строке каждого набора входных данных содержится $$$n$$$ ($$$1 \le n \le 100$$$) — размер массива.

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

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

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

Пример
Входные данные
4
7
2 4 6 7 8 9 10
2
55 55555
4
1000000 1000 1 1000000000
5
23 32 23 32 23
Выходные данные
2
5
1000000
23
Примечание

В первом наборе входных данных дан массив $$$[2, 4, 6, 7, 8, 9, 10]$$$.

При выборе индексов $$$[1, 3, 4, 6, 7]$$$ удаляется $$$a_4 = 7$$$, и получается массив $$$[2, 4, 6, 8, 9, 10]$$$.

Затем при выборе индексов $$$[2, 5, 6]$$$ удаляется $$$a_5 = 9$$$, и получается массив $$$[2, 4, 6, 8, 10]$$$. Получить ответ больше $$$2$$$ невозможно.