Red Blue Hackenbush

This problem was created by Clive Fraser - many thanks!

Red Blue Hackenbush is an energetic game played by two people wielding axes. They begin by choosing a group of special bushes (small trees) called Hackenbushes. They prepare the bushes by taking each branch in turn and painting the branch either red or blue; chosen at random. When the game starts, the two players take it in turn to select one of the bushes and to hack off one of its branches. However, one of the players (referred to as RED) can only hack off red branches, while the other player (BLUE) can only hack off the blue branches. When a branch is hacked off, it is no longer part of the bush and any other branches which are attached to the hacked off branch are also no longer part of the bush. So each move results in the removal of at least one branch from one of the remaining bushes. The first player who is unable to make a move loses the game.

If both players play optimally then the result of the game can be determined at the start. Nevertheless, optimal moves are not always obvious so the game can still be enjoyable to play. Interestingly, it can be shown that, if both players play optimally, any game of Hackenbush must have one of three possible outcomes. Either RED will win, whoever plays first. Or BLUE will win, whoever plays first. Or the game will be won by the second player, whoever plays first. There are no Hackenbush games where the winner will be the first player, whoever goes first.

The Hackenbushes in this problem all have a binary tree structure. They have a single branch (or stem) linking them to the ground. This branch can split into 1 or 2 higher branches. These in turn can each split into 1 or 2 higher branches, and so on. The Hackenbushes have branches at 4 different levels. If all splits are into 2 higher branches we will have 1 branch at level 1 (the stem), 2 branches at level 2, 4 branches at level 3 and 8 branches at level 4. Such a Hackenbush has 15 branches. Hacking off the branch at level 1 is equivalent to removing the entire tree. Hacking off any other branch removes that branch and all higher level branches which are connected to it.

In this problem you will be given a number of Hackenbush games and must determine the outcome, assuming optimal play. Each game is to be designated either R (RED wins whoever goes first) or B (BLUE wins whoever goes first) or 2 (the second player wins whoever goes first). No game will contain more than 10 bushes and no bush will have more than 4 levels or more than 15 branches.

In order to describe a game it is necessary to have a short and simple description for a bush. Since the bush can have up to 15 branches we will use a string of 15 characters to describe the bush. These will be R for a red branch, B for a blue branch and * for a missing branch. The first character in the string is the colour of the single branch at level 1 (the stem). The next two characters are the colours of the 2 branches at level 2, going from left to right. The next four characters are the colours of the 4 branches at level 3, going from left to right. The next eight characters are the colours of the 8 branches at level 4, going from left to right.

The first of the three diagrams below relates the branches in the bush to the position of the characters in the 15-character bush description. If we label the characters from 1 to 15 using the hexadecimal digits 1 to F, then the bush description 123456789ABCDEF gives rise to the first of the three bush diagrams. The second of the bush diagrams is derived from the bush description RRBBR*RBR*B**RB. Notice that there are only 11 branches in this bush. The four missing branches are represented by the * character in the bush description. If we hack off the blue branch in position 3 of this second bush, we convert it into the third bush, which has the bush description RR*BR**BR*B****.

8     9   A     B   C     D   E     F     B     R         B             R     B     B     R         B
 8   9     A   B     C   D     E   F       B   R         B               R   B       B   R         B
  8 9       A B       C D       E F         B R         B                 R B         B R         B
   44       55         66       77           BB       RR                  RR           BB       RR
     4     5             6     7               B     R                   R               B     R
      44 55               66 77                 BB RR                  RR                 BB RR
        222               333                     RRR               BBB                     RRR
           2222       3333                           RRRR       BBBB                           RRRR
               222 333                                   RRR BBB                                   RRR
                  1                                         R                                         R
                  1                                         R                                         R
                  1                                         R                                         R

Input/Output description: The first line of the input data will contain an integer G for the number of games. G lines will follow. Each of these lines begins with an integer N for the number of bushes in the game. The rest of the line contains N bush description strings. All are separated by spaces. For each game, assuming optimal play, designate the result as R, B or 2. Combine all of your answers into a single string, separated by spaces.

Example:

input:
3 
3 BR************* B*R************ R**************
3 RRBB*RB*R****R* RBBRRBRRR*RRR*B BBRRBBR**BBR**R
4 BRRBBBB*RB*RBRB BBBBB*B*RBR***B RRRRRRBRB*RR*** RBBRBBRR*BBBR**

answer:
2 R B