Совсем недавно Егор узнал про алгоритм Евклида нахождения наибольшего общего делителя двух чисел. Наибольшим общим делителем двух чисел \(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
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач