G. НОД на клетчатом поле
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Совсем недавно Егор узнал про алгоритм Евклида нахождения наибольшего общего делителя двух чисел. Наибольшим общим делителем двух чисел $$$a$$$ и $$$b$$$ называется наибольшее число, на которое $$$a$$$ и $$$b$$$ делятся без остатка. С помощью этих знаний Егор может решить задачу, которую он когда-то не решил.

У Василия есть клетчатое поле $$$n$$$ строк на $$$m$$$ столбцов, на пересечении $$$i$$$-й строки и $$$j$$$-го столбца находится число $$${a_i}_j$$$. Егор хочет попасть из левого верхнего угла (на пересечении первой строки и первого столбца) в правый нижний угол (на пересечении последней строки и последнего столбца) и узнать, какой НОД у всех чисел на пути. Разрешается двигаться только вниз и вправо. Егор выписал несколько путей и получил разные значения НОД, ему стало интересно, какой максимальный НОД можно получить.

К сожалению, Егор устал считать НОД чисел и поэтому просит Вас помочь ему найти максимальный НОД чисел на пути из левого верхнего угла в правый нижний угол клетчатого поля.

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

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le {10}^{4}$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 100$$$) — количество строк и столбцов клетчатого поля.

Далее следует $$$n$$$ строк, $$$i$$$-я строка содержит $$$m$$$ целых чисел $$$(1 \le a_{i,j} \le {10}^{6}$$$) — числа, записанные в $$$i$$$-й строке и $$$j$$$-м столбце клетчатого поля.

Гарантируется, что сумма $$$n \cdot m$$$ не превосходит $$$2 \cdot {10}^{5}$$$ по всем тестовым случаям.

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

Для каждого набора входных данных в отдельной строке выведите максимальное возможный НОД на пути из клетки левой верхней клетки в правую нижнюю клетку.

Пример
Входные данные
3
2 3
30 20 30
15 25 40
3 3
12 4 9
3 12 2
8 3 12
2 4
2 4 6 8
1 3 6 9
Выходные данные
10
3
1