Решите пожалуйста олимпиадную задачу

Лере на день рождения подарили клетчатое поле, состоящее из n строк и m столбцов и фишку. Спросите зачем фишку? Чтобы она могла передвигать фишку по клетчатому полю. Каждый день Лера придумывает новую игру с этими предметами и сегодняшний день не стал исключением.

Сначала Лера написала в каждой клетке поля целое число a_ij (1≤a_ij≤10⁶). После этого она решила поставить фишку на поле (1,1) и придумала следующие правила перемещения фишки: за один ход Лера может переместить фишку с поля (i1,j1) на поле (i2,j2), если НОД(a_i1j1,a_i2j2)>1. Лере стало интересно — за какое минимальное количество ходов она сможет переместить фишку с поля (1,1) на поле (n,m). Спустя несколько секунд она смогла понять, сколько ходов ей потребуется. А сможете ли вы?

Входные данные
В первой строке записано два целых числа n и m (1≤n≤5⋅10⁵,1≤m≤5⋅10⁵,1≤n⋅m≤5⋅10⁵) — количество строк и столбцов в клетчатом поле.

В каждой из следующих n строк записано по m целых чисел a_ij (1≤a_ij≤10⁶) — значения в клетках.

Выходные данные
Выведите единственное целое число — минимальное количество ходов, чтобы переместить фишку из клетки (1,1) в клетку (n,m). Если это сделать невозможно, выведите −1.


Примеры
входные данные
1 1
1
выходные данные
0
входные данные
3 1
1
2
4
выходные данные
-1
входные данные
3 3
6 9 5
8 6 21
77 14 11
выходные данные
3
Примечание
Наибольший общий делитель НОД(a,b) двух положительных целых чисел a и b равняется самому большому целому числу, на которое без остатка делятся оба числа a и b

0

Смысл олимпиад в том, что их надо решать самостоятельно. Расскажите до чего дошли. Если будет смысл - помогу.

3