Hex Board State

Hex is a board game that Piet Hein and John Nash designed independently of each other. This problem borrows the idea, but you do not need to have played Hex.

The game is played on an $N \times N$ board whose cells are hexagons. One player uses red stones and the other uses blue stones. The board starts empty, and the two players take turns placing one stone of their own color on a single cell of the board. A player may place a stone on any cell that no stone of either color occupies, and a stone does not have to go next to another stone of the same color. Which player moves first is chosen at random, with equal probability for the two players.

The upper and lower sides of the board are marked red, and the other two sides are marked blue. The goal is to link the two sides marked with your own color by a connected group of your own stones, and the first player to do that wins. Each of the four corner cells counts as touching both colors. The game ends the moment one player wins.

Write the position of a cell as row $i$ from the top and column $j$ from the left. The cells next to cell $(i, j)$ are those of $(i-1, j)$, $(i-1, j+1)$, $(i, j-1)$, $(i, j+1)$, $(i+1, j-1)$ and $(i+1, j)$ that lie on the board. Stones of the same color form one connected group when you can walk from one to the other through cells that are next to each other. Red wins by linking row $i = 1$ to row $i = N$, and blue wins by linking column $j = 1$ to column $j = N$.

Given a board position, report its status. The answer is one of these four.

• Impossible: the two players could not have reached this position while following the rules.
• Red wins: the player with the red stones has won.
• Blue wins: the player with the blue stones has won.
• Nobody wins: nobody has won yet. A game of Hex never ends in a draw, so the game is still open.

For a position that cannot be reached, the only correct answer is Impossible, even if red or blue already has a connected group linking the two sides marked with that color.

The first line contains the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains the side length of the board, $N$. The next $N$ lines each contain a string of length $N$ made up only of the characters B, R and .. B is a cell holding a blue stone, R is a cell holding a red stone, and . is an empty cell.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the status of the board: Impossible, Blue wins, Red wins or Nobody wins. The judge is case sensitive, so impossible, blue wins, red wins and nobody wins are wrong answers.