Hex is a game for two players, played on a diamond-shaped board with hexagonal cells. At the start of the game, all cells are empty. Each player in turn puts a stone of his own color (black or white) in any empty cell. The goal for Black is to connect the top left edge of the board with the bottom right edge, by making a path consisting of neighboring cells with Black stones in them. White attempts to make a path from the top right to the bottom left. The cells located in the corners of the diamond count as being adjacent to both corresponding edges. The player to start the game is Black. An interesting feature of this game is that there is always a winner: if all cells are filled and one player does not have a path connecting his designated edges, then the other player automatically does have one.
The game situation as described by the first test case in the sample input. Black has successfully connected the top left edge and the bottom right edge and has therefore won the game.
Write a program which, given a game situation, determines which player has won, or that the game has not yet finished.
On the first line one positive number: the number of test cases, at most 100. After that per test case:
The number of cells with black stones is equal to, or one more than, the number of cells with white stones. The game situation can be such that one of the players had already won a few turns earlier.
Per test case:
3 7 .WBW... .BW.WW. .BBWBB. ..BBWB. ..BWBW. ..BWB.. .WWWB.. 5 ..B.. .BBWB WWWBW B.WWB .B... 4 BBWB WWB. BWWB BWBW
Black wins White wins Not finished