지뢰 지도

어느 조직이 중요한 문제집을 보관하기 위해 거대한 미로 형태의 금고를 지었다. 이 금고는 방들이 한 변의 길이가 홀수인 정사각형 격자로 배열되어 있으며, 각 방은 격자에서의 (행, 열) 좌표로 구분된다. 서로 이웃한 방들은 문으로 연결되어 있다.

침입을 어렵게 하기 위해 일부 방에는 지뢰가 설치되어 있다. 다행히 침입자는 지뢰 탐지기를 가지고 있는데, 이 탐지기는 어느 방에서든 사용할 수 있으며 현재 방에 인접한 최대 8개의 방 중 지뢰가 있는 방이 하나라도 있는지 여부만 알려 준다. 지뢰가 몇 개인지, 어느 방향인지는 알 수 없다.

침입자는 중앙 방에서 출발한다. 중앙 방에는 지뢰가 없음이 보장된다. 그는 다음과 같은 단순한 전략을 따른다.

• 현재 방에서 탐지기가 "인접한 지뢰 없음"이라고 알리면, 인접한 8개의 방을 모두 안전하게 탐색(이동)할 수 있다. 이런 방은 . 로 표시한다.
• 탐지기가 "인접한 지뢰 있음"이라고 알리면, 위험을 무릅쓰지 않고 그 방에서 더 나아가지 않는다(후퇴). 이런 방은 # 로 표시한다. 다만 이런 방도 나중에 다른 안전한 경로를 통해 도달할 수 있으므로, 도달한 방으로 취급하여 여전히 # 로 표시한다.

즉, 중앙에서 출발하여 위 규칙으로 도달할 수 있는 모든 방을 . 또는 # 로 표시한다. 지뢰가 있는 방은 * 로, 끝내 도달할 수 없는 방은 ? 로 표시하라.

각 금고 설계도에 대해 이 지도를 만들어 출력하는 것이 여러분의 과제이다.

첫 번째 줄에 시나리오(금고 설계도)의 개수가 주어진다.

각 시나리오는 금고 한 변의 길이인 홀수 정수 $n$ ($1 < n < 300$) 이 적힌 줄로 시작한다. 다음 줄에는 지뢰의 개수 $m$ 이 주어진다($m$ 은 1 이상이며 방의 총 개수를 넘지 않는다). 이어서 $m$ 개의 줄에 각각 두 정수 $r$ 과 $c$ ($1 \le r, c \le n$) 가 주어지며, 이는 지뢰가 있는 방의 행과 열을 뜻한다.

각 시나리오에 대해 먼저 Scenario #i: 를 출력한다. 여기서 $i$ 는 1부터 시작하는 시나리오 번호이다. 그 다음 위에서 설명한 금고 지도를 $n$ 개의 줄로 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.