Совсем недавно Егор узнал про алгоритм Евклида нахождения наибольшего общего делителя двух чисел. Наибольшим общим делителем двух чисел $$$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}$$$ по всем тестовым случаям.
Для каждого набора входных данных в отдельной строке выведите максимальное возможный НОД на пути из клетки левой верхней клетки в правую нижнюю клетку.
32 330 20 3015 25 403 312 4 93 12 28 3 122 42 4 6 81 3 6 9
10 3 1
| Codeforces Round 938 (Div. 3) |
|---|
| Закончено |
