题目描述

The game of Hex is played in a rhombus board shown below. In which the cells are regular hexagons.

:::align{center} :::

Two players take turns to move. In each move, the first player puts a white piece on the board and the second player puts a black piece on the board. If the white pieces connect the top side and the bottom side of the board, then the first player wins. If the black pieces connect the left side and the right side of the board, then the second player wins. Both players put their pieces randomly. That is, if there are $k$ empty cells, each of them will be chosen by $1/k$ chance. Given a board with some pieces on it, your task is to calculate the probability that each player will win. Note that the player with white pieces moves first, no matter how many pieces are on the board at the beginning.

输入格式

The first line is the number of test cases up to 20. For each test case, the first line is an integer $n$ ($0 < n < 9$), which is the size of the board. Then there are $n$ rows describing the given board. For each row, there are $n$ non-space characters. Where 'W' is a white piece, 'B' is a black piece, and '.' is an empty cell. There are $i - 1$ leading spaces in the $i$-th row and there is a space between adjacent non-space characters. There is an empty line after each test case.

输出格式

For each test case, output the winning probability of each player with the precision of 6 digits.

2
4
. B W B
 B W B W
  W B W B
   . W B .

5
. B B . .
 B . B . .
  . B . B B
   . B B . .
    W W W W W

White 0.666667 Black 0.333333
White 0.000000 Black 1.000000