Hex 游戏是在如下图所示的菱形棋盘上进行的，棋盘上的格子是正六边形。

两名玩家轮流落子。每一回合，先手玩家在棋盘上放置一枚白子，后手玩家在棋盘上放置一枚黑子。如果白子连接了棋盘的顶边和底边，则先手玩家获胜。如果黑子连接了棋盘的左边和右边，则后手玩家获胜。两名玩家均随机放置棋子。也就是说，如果当前有 $k$ 个空位，每个空位被选中的概率均为 $1/k$。给定一个已经放置了部分棋子的棋盘，你的任务是计算每位玩家获胜的概率。注意，无论棋盘初始状态有多少棋子，执白子的玩家总是先手。

输入格式

第一行是一个整数，表示测试用例的数量（最多 20 个）。对于每个测试用例，第一行是一个整数 $n$ ($0 < n < 9$)，表示棋盘的大小。接下来有 $n$ 行描述给定的棋盘。对于每一行，包含 $n$ 个非空格字符。其中 'W' 代表白子，'B' 代表黑子，'.' 代表空位。第 $i$ 行有 $i-1$ 个前导空格，且相邻的非空格字符之间有一个空格。每个测试用例后有一个空行。

输出格式

对于每个测试用例，输出每位玩家获胜的概率，保留 6 位小数。

样例

样例输入 1

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

样例输出 1

White 0.666667 Black 0.333333
White 0.000000 Black 1.000000