Hex (Large)

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

The game is played on an $N \times N$ board whose cells are hexagons. Two players take part: Red, who uses red stones, and Blue, who uses blue stones. The board starts empty, and the players alternate placing one stone of their own color on one cell. A stone may go on any cell that holds no stone of either color, and there is no requirement to place it next to a stone of the same color. Which player moves first is decided at random, each with probability one half.

The upper and lower sides of the board are marked red, and the other two sides are marked blue. A player wins by being the first to form a connected chain of their own stones joining the two sides marked with that player's color. Each of the four corner cells counts as touching both colors. The game ends the moment one player wins.

Number the rows $1$ to $N$ from top to bottom and the columns $1$ to $N$ from left to right. Each row is shifted half a cell to the right of the row above it, so the cells sharing an edge with cell $(r, c)$ are $(r, c-1)$, $(r, c+1)$, $(r-1, c)$, $(r-1, c+1)$, $(r+1, c-1)$ and $(r+1, c)$, leaving out any that fall outside the board. Red joins row $1$ to row $N$, and Blue joins column $1$ to column $N$.

Given a position, report which of the following it is.

• 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 cannot end without a winner.

For an impossible position the only correct answer is Impossible, even when Red or Blue has already formed a chain joining the two sides marked with that color.

Here is a game on a $6 \times 6$ board that Blue won. Blue moved first and placed a blue stone on the cell marked $1$, then Red played on cell $2$, then Blue on cell $3$, and so on. Blue wins as the eleventh stone goes down.

The first line of input holds the number of test cases, $T$. $T$ test cases follow. Each test case starts with the side length of the board, $N$. The next $N$ lines each hold $N$ characters drawn from '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 100$

For each test case, print one line of 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 judged incorrect.