Дана табличка n × n, в клетках которой записаны натуральные числа от 1 до 109.

Существует ли путь из клетки (1, 1) в клетку (n, n) такой, что НОД чисел на этом пути больше 1? Перемещаться можно по клеткам только вправо и только вниз. Например, из клетки с координатами (x, y) можно перейти в клетку (x, y + 1) или в клетку (x + 1, y).

Формат ввода
В первой строке вводится n — сторона таблички.

В следующих n строках вводится по n чисел — сама таблица.

Формат вывода
Если путь существует, то выведите 0 при перемещении вправо и 1 при перемещении вниз. Если удовлетворяющих условию путей несколько, то выведите любой подходящий путь.

Если пути не существует, выведите -1.

НА ЛЮБОМ ЯЗЫКЕ