Two Colour Special Nim

This problem was created by Clive Fraser - many thanks!

Ann and Bob enjoy playing Nim games and inventing new rules for different games. A typical game has several piles of discs. The players take it in turn to remove discs (according to the rules) and the first player to have no valid moves left loses the game.

For their new game Ann and Bob decided to have discs of two different colours, black and white. Each player would be assigned a colour and could only remove discs of their own colour. They decided that players should be able to remove a disc from any position in any of the piles. After a little thought they realised that, if players removed one disc at a time, that the game would be trivially determined by the number of discs of each colour. What they needed was a rule that allowed more than one disc to be removed, if special circumstances applied. After a little more thought, they realised that it was never going to be advantageous for a player to remove more than 1 of their own pieces. The solution was to allow a special move where a player (after removing their own piece) can remove one or more of their opponent's pieces. This led to the following rules for the game.

The game starts with several vertical piles of discs. Some of the discs are black and the others are white. Any combination of discs can occur in any pile. One player is chosen to start. The players then take it in turns to remove discs until one of the players has no valid moves remaining. One player (Black) can remove only black discs (except in a Special move). Similarly, the other player (White) can only remove white discs (except in a Special move). For a normal (non-special) move a player must remove one of their own discs from any position and from any pile. A Special move is made in place of a normal move if any pile has the top disc in the current player's colour and the disc immediately below this is in the opponent's colour. The player can now remove the top disc (of their own colour) together with a group of one or more discs below this, if these are all of the opponent's colour.

To illustrate this, consider the following pile of black and white discs (B and W). BWWWBWWBBW. This is a pile of 10 discs (6 white and 4 black). The leftmost disc (B) represents the top of the pile. The final disc (W) is at the bottom. If it is black's move we have the conditions which allow a Special move. In fact black has 3 possible moves available with this pile. The Special move requires black to remove the top black disc together with the group of 3 white discs immediately below it. This changes the pile to BWWBBW. Notice that none of the other white discs are removed because they are not part of the group below the top disc. Black could also have made two normal moves with this pile. Removing the 5th disc in the pile results in BWWWWWBBW. Even though there are two white discs immediately below this black disc, they cannot be removed because the Special move only applies when the black disc is at the top of the pile. The other normal move for black is to remove either disc 8 or disc 9 from the pile, leaving BWWWBWWBW. White has only 3 normal moves available with this pile. These lead to BWWBWWBBW, BWWWBWBBW or BWWWBWWBB. Of course, white is also able to make Special moves when they are available. White can make a Special move with the pile WBWWB to leave WWB.

Ann and Bob enjoyed playing a number of games with their new rules. As they played they were able to determine the optimum strategy for the game. If both players play with this optimum strategy, the outcome of the game is determined before any moves are played. However, Ann and Bob were interested to notice that almost every randomly generated game (even with equal numbers of black and white discs), when played optimally by both players, was a win for either black or white, irrespective of which player plays first. In only a very small number of cases, it does make a difference who plays first.

In this problem you will be given a number of randomly generated games. For each of these you are asked to determine which of White or Black wins the game, if both play optimally. It is guaranteed that the result is the same whichever player makes the first move. Piles of discs will be represented as strings of characters B and W, with the leftmost character representing the top disc in the pile. These strings will be separated by single spaces. The number of piles will vary between 3 and 12. The number of discs in a pile will vary between 1 and 14.

Input/Output description: The first line of the input data will contain a single integer N, for the number of games. There are 2 lines of data for each game. The first of these consists of a single integer P, for the number of piles of discs. The second line contains P space-separated strings for each of the P piles of discs. Find the winner of the game, assuming optimal play, giving the answer as W or B. Combine all answers into a single string, separated by single spaces.

Example:

input:
4
3
WBWBWWBBBWBW BWBWWBWWBB WWBWBWBWBWWBBB
4
WBWWWBWWBWW BBWBWWBBWBBBBB BBBWWWWWBBWBWW WWBBWBWBWBBW
5
WBBWWWWWWBBBBB BWBBBWWBWWWWBW WBBWWBWBBBBBBB WBWBBWWWWWWBB BWBWBWBWBWBBBB
6
BBWWWBWWWWW BWWBBWWWBWWWBW BBBBWWWBBWBWBW WWBWWWWBWBBBBB BWBBWBBWWBBWBB WBBWBWWWWWWBW

answer:
B B W W