Совсем недавно Егор узнал про алгоритм Евклида нахождения наибольшего общего делителя двух чисел. Наибольшим общим делителем двух чисел \(a\) и \(b\) называется наибольшее число, на которое \(a\) и \(b\) делятся без остатка. С помощью этих знаний Егор может решить задачу, которую он когда-то не решил.
У Василия есть клетчатое поле \(n\) строк на \(m\) столбцов, на пересечении \(i\)-й строки и \(j\)-го столбца находится число \({a_i}_j\). Егор хочет попасть из левого верхнего угла (на пересечении первой строки и первого столбца) в правый нижний угол (на пересечении последней строки и последнего столбца) и узнать, какой НОД у всех чисел на пути. Разрешается двигаться только вниз и вправо. Егор выписал несколько путей и получил разные значения НОД, ему стало интересно, какой максимальный НОД можно получить.
К сожалению, Егор устал считать НОД чисел и поэтому просит Вас помочь ему найти максимальный НОД чисел на пути из левого верхнего угла в правый нижний угол клетчатого поля.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите максимальное возможный НОД на пути из клетки левой верхней клетки в правую нижнюю клетку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|