Othello

Time Limit: 1 Second    Memory Limit: 32768 KB

Before asking you to predict the winner of the Othello game, a description of the game is given below:

CONTENTS

- Othello game board has 64 squares, plus storage compartments with roll-down covers on both sides for discs.

- 64 discs: white on one side, black on the other.

PREPARATION

Fill each compartment with 32 discs.

OBJECT OF THE GAME

To outflank your opponent and flip your opponent's discs to your color, ending up with the majority of discs on the board in your color.

GAME RULES

1. Each player chooses one color to use throughout the game.

2. Black places two black discs, and White places two white discs on the board as shown in Figure 1. The game always begins with this set-up.

 

3. Players choose who goes first.

4. A move consists of taking a disc from the compartment and placing it so that it completes the outflanking of one or more opposite color discs, then flipping the outflanked disc(s) over to your color.

For example, white disc A is already in place on the board. By the placement of white disc B, the black row of discs has been outflanked.

Thus all the captured discs are flipped and this row becomes . . .

5. A PLAYER MUST ALWAYS OUTFLANK HIS OPPONENT AND FLIP AT LEAST ONE OPPOSING DISC IN ORDER TO MOVE.
If he cannot make a move, he loses his turn and his opponent moves. This is called a PASS.

6. A disc may outflank any number of opposing discs in one or more rows. (A row may be one disc or many discs in a straight line.)

7. A disc may outflank in any direction: horizontal, vertical, diagonal, forward or backward.

8. A disc may outflank in any number of directions at the same time. (Theoretically, it is possible to flip in up to 8 directions at once.) DISCS MAY ONLY BE FLIPPED AS A DIRECT RESULT OF A MOVE.

9. The game is over when the board is entirely filled with discs, or when it is not possible for either player to move (i.e., out flank an opponent's row and flip an opponent's disc), or when the board is filled (or partially filled) with all one color.
At this point, discs are counted up. The player with the most discs is the winner.

Now given a configuration of the Othello game, what is the maximum possible advantage the black can gain after T moves? The formula of advantage is the number of black discs minus the number of white discs.

Note:

1. Pass is also considered as one move.

2. Assume the game is never end. The players just keep pass on the end of game.

3. Assume both of the players may make mistakes.

4. Assume it is always black's turn.

Input

The input begins with an integer n, indicates the number of test cases. For each test case, the first line gives an integer t (0 < t <= 4), and the following 8 lines give a valid configuration. Every line contains 8 characters, 'B' for black and 'W' for white.

Output

For each test case, output an integer indicates the maximum advantage the black can gain.

Sample Input

1
1

BW 
WB 

Sample Output

3

Submit

Source: ZOJ Monthly, November 2003