견제 미로찾기

$N \times N$ 크기의 격자로 표현되는 미로가 있다. 미로의 좌상단은 $(1,1)$이고 우하단은 $(N,N)$이다. $0$은 이동할 수 있는 길, $1$은 이동할 수 없는 벽이 있는 칸을 뜻한다. 처음에 게임 말 하나가 $(1,1)$에 놓여 있다. 건이와 준성이는 번갈아 가며 다음 두 가지 행동 중 하나를 취할 수 있다.

1. 게임 말을 $x$ 또는 $y$ 좌표가 증가하는 방향으로 $1$ 이상 $K$ 이하만큼, 한 방향으로만 이동한다. 벽이 있는 칸에 도착하거나 벽을 통과하여 이동할 수는 없다.
2. $K$를 $K$보다 작은 $K$의 양의 약수 중 하나로 변경한다.

자신의 차례에 아무 행동도 할 수 없는 사람이 패배한다. 게임은 건이부터 시작하며, 두 사람이 최선을 다해 게임을 진행했을 때 누가 이길지 구하시오.

첫 번째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 미로의 정보가 공백으로 구분되어 주어진다.

건이가 이기면 $1$, 준성이가 이기면 $0$을 출력한다.

• $1 \leq N \leq 300$
• $1 \leq K \leq N$
• $N$, $K$는 양의 정수이다.
• 미로는 $0$ 혹은 $1$로 이루어져 있다.
• 미로의 $(1,1)$은 $0$임이 보장된다.