Hex

Hex is a game for two players, played on a diamond-shaped board of hexagonal cells. At the start all cells are empty. The players take turns; on each turn a player places a stone of their own colour (black or white) in any empty cell.

Black's goal is to connect the top-left edge of the board with the bottom-right edge by forming a path of neighbouring cells that all contain black stones. White tries to form a path of white stones from the top-right edge to the bottom-left edge. A cell located in a corner of the diamond counts as belonging to both edges that meet at that corner.

Black moves first. Hex has the property that there is always a winner once the board is full: if every cell is filled and one player has no connecting path, then the other player necessarily does.

Given a game situation, determine which player has won, or that the game is not yet finished.

The first line contains one positive integer: the number of test cases, at most 100. Each test case is given as follows:

• One line with an integer $n$ ($2 \le n \le 100$): the size of the board (the number of cells along each edge).
• $n$ lines, each with $n$ characters, describing the diagonals of the board. The $i$-th of these lines lists the contents of the $i$-th diagonal, ordered from the diagonal along the top-left edge (given first) to the diagonal along the bottom-right edge (given last). Within a line, the first character is the cell on the bottom-left edge and the last character is the cell on the top-right edge. Each character is B, W, or ., denoting a black stone, a white stone, or an empty cell.

The number of black stones equals the number of white stones, or is exactly one more. The situation may be one in which a player had already won several moves earlier.

For each test case, output one line containing Black wins, White wins, or Not finished, indicating the status of the game.