Mine Map

An organization has built a giant maze-like vault to store an important problemset. The vault is a square grid of rooms whose side length is odd; each room is identified by its (row, column) coordinates, and adjacent rooms are connected by doors.

To make intrusion harder, mines are placed in some of the rooms. Fortunately, an intruder carries a mine detector. The detector can be used from any room and reports only whether at least one of the up to eight rooms adjacent to the current room contains a mine — never how many, and never in which direction.

The intruder starts in the center room, which is guaranteed to contain no mine, and follows this simple strategy:

• If the detector reports no adjacent mine in the current room, all eight surrounding rooms can be searched (entered) safely. Mark such a room with ..
• If the detector reports one or more adjacent mines, the intruder does not risk advancing any farther from that room (a retreat). Mark such a room with #. Such a room may still be reached later through another safe route, so it counts as reached and remains marked #.

In other words, mark every room reachable from the center under this rule with . or #. Mark every room that contains a mine with *, and mark every room that can never be reached with ?.

For each vault blueprint, output this map.

The first line contains the number of scenarios.

Each scenario begins with a line containing the odd integer $n$ ($1 < n < 300$), the side length of the vault. The next line contains the number of mines $m$ ($m$ is at least 1 and does not exceed the number of rooms). Then follow $m$ lines, each containing two integers $r$ and $c$ ($1 \le r, c \le n$), the row and column of a mine.

For each scenario, first print Scenario #i:, where $i$ is the scenario number starting at 1. Then print the vault map described above on $n$ lines. Print a blank line between two consecutive scenarios.