Фишка

from math import gcd
from collections import deque
 
def min_moves(n, m, grid):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    visited = [[False]*m for _ in range(n)]
    queue = deque([(0, 0, 0)])
 
    while queue:
        x, y, d = queue.popleft()
        if (x, y) == (n-1, m-1):
            return d
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and gcd(grid[x][y], grid[nx][ny]) > 1:
                visited[nx][ny] = True
                queue.append((nx, ny, d+1))
    return -1
 
print(min_moves(1, 1, [[1]]))
print(min_moves(3, 1, [[1], [2], [4]]))
print(min_moves(3, 3, [[6, 9, 5], [8, 6, 21], [77, 14, 11]]))

from math import gcd
from heapq import heappush, heappop
 
def min_moves(n, m, grid):
    visited = [[False]*m for _ in range(n)]
    heap = [(0, (0, 0))]
 
    while heap:
        d, (x, y) = heappop(heap)
        if (x, y) == (n-1, m-1):
            return d
        if visited[x][y]:
            continue
        visited[x][y] = True
        for i in range(n):
            for j in range(m):
                if not visited[i][j] and gcd(grid[x][y], grid[i][j]) > 1:
                    heappush(heap, (d+1, (i, j)))
    return -1
 
print(min_moves(1, 1, [[1]]))
print(min_moves(3, 1, [[1], [2], [4]]))
print(min_moves(3, 3, [[6, 9, 5], [8, 6, 21], [77, 14, 11]]))

b, a = map(int,input().split())
m = []
for _ in range(b):
    m.append([int(j) for j in input().split()])