A Random Turn Connection Game

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Alice and Bob play a random turn connection game in a square board with 8×8 cells. In each move, a player tosses a fair coin to decide who gets the move. That is, both Alice and Bob will get the next move with 50% chance, no matter who has moved before. Once a player gets a move, she will place a piece in an empty cell. Both Alice and Bob play randomly. That is, if there are k empty cells, each cell will be chosen with 1/k chance. Once Alices pieces connect the top side and the bottom side of the board, she will win the game. Similarly, once Bobs pieces connect the left side and the right side of the board, he will win the game. Pieces only connect horizontally or vertically, and cannot connect diagonally. Your task is to calculate the winning probabilities of Alice and Bob.

Input

The first line is the number of test cases. Each test case contains 8 lines and each line contains 8 characters, representing the current status of the board. The cells occupied by Alice are marked as “A”, the cells occupied by Bob are marked as “B”, and the empty cells are marked as “.”. There is an empty line between test cases.

Output

For each test case, output the probability that Alice and Bob will win with the precision of 6 digits.

Sample Input

4 ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... BBBB.BBB ....A... ....A... ....A... ....A... ....A... ....A... BBBBA... ...ABBBB ...A.... ...A.... ...A.... ........ ........ ........ ........ ........ ........ ........ .......A

Sample Output

Alice 1.000000 Bob 0.000000 Alice 0.500000 Bob 0.500000 Alice 0.000000 Bob 0.000000 Alice 0.223093 Bob 0.198498

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

提交代码