저주받은 게임

당신은 창고에서 골동품 상자를 발견하고 열어 보기로 했다. 상자를 여는 순간 당신은 악마와 겨루는 저주받은 게임에 갇힌다. 게임은 333라운드로 이루어지며, 탈출하려면 모든 라운드를 이겨야 한다. 악마는 게임 내내 쓸 수 있는 동전 999개도 준다.

이 문제에서 격자의 칸 $(r, c)$는 $r$행 $c$열에 있는 칸을 뜻한다.

각 라운드가 시작하기 전에 악마는 $3$행 $3$열 격자 모양의 비밀 종이를 준비한다. 행과 열은 모두 1부터 3까지 번호가 매겨져 있다. 악마는 비밀 종이의 칸 중 하나 이상의 칸에 몰래 구멍을 뚫으며, 당신은 어느 칸에 구멍이 있는지 알 수 없다. 이후 악마가 홀수 정수 $N$ ($3 \le N \le 33$)을 주면 라운드가 시작된다.

각 라운드에서 당신은 질의를 여러 번 할 수 있으며, 질의마다 동전 1개가 든다. 질의할 때마다 당신은 악마에게 당신의 종이를 준다. 이는 $N$행 $N$열 격자이며, 행과 열은 모두 1부터 $N$까지 번호가 매겨져 있다. 당신은 각 칸을 검은색 또는 흰색으로 칠한다.

질의마다 악마는 $N-2$행 $N-2$열의 이진 결과 격자를 계산한다. 행과 열은 1부터 $N-2$까지 번호가 매겨져 있다. 결과 격자의 $(r, c)$ 칸 값은 다음과 같이 정해진다.

• 악마는 비밀 종이를 당신의 종이 위에 올리되, 당신의 종이의 $(r+i-1, c+j-1)$ 칸이 비밀 종이의 $(i, j)$ 칸과 겹치도록 놓는다. 여기서 $1 \le i, j \le 3$이다.
• 악마는 비밀 종이의 해당 칸에 구멍이 있을 때에만 당신의 종이에서 그 칸의 색을 볼 수 있다.
• 결과 격자의 $(r, c)$ 칸 값은 구멍을 통해 보이는 검은 칸의 개수가 홀수이면 1, 아니면 0이다.

결과 격자의 값이 모두 1이면 당신은 라운드를 이긴다. 그렇지 않으면 악마가 결과 격자를 피드백으로 주고 라운드가 계속된다.

동전을 모두 쓰고도 모든 라운드를 이기지 못하면 당신은 영원히 갇힌다. 저주받은 게임에서 탈출하라!