题目背景

译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta G.

2025/3/19：加入一组来自 @lmh 的 hack 数据，位于 Subtask 0。

题目描述

有一个 $n\times m$ 的矩阵，左上角的格子记为 $(1,1)$，右下角的格子记为 $(n,m)$。

格子要么是黑色的，要么是白色的。魔法少女从 $(1,1)$ 出发寻找食物，按照如下规则移动：

• 每次可以向上下左右移动一步，但是不能出界。
• 如果移动到黑色格子，则无事发生。
• 如果移动到白色格子，魔法少女会被等概率独立随机传送到任意一个白色格子（包括她所在的格子）上。传送完后可以继续移动。

当魔法少女到达 $(n,m)$ 时，她会停止移动。魔法少女会最小化移动的期望次数。求出魔法少女移动的期望步数。

题目保证 $(1,1)$ 和 $(n,m)$ 都是黑色的。

输入格式

本题单个测试点内含有多组测试数据。

第一行，一个正整数 $T$，表示数据组数。

接下来依次描述 $T$ 组数据：

每组数据第一行，两个正整数 $n,m$。

接下来一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列的字符是 $\texttt{C}$，表示 $(i,j)$ 是黑色；否则是 $\texttt{B}$，表示 $(i,j)$ 是白色。

输出格式

可以证明答案一定是一个有理数。

对于每组数据，输出一行一个既约分数 $p/q$。

3
2 2
CC
CC
2 2
CB
BC
1 12
CBCCCCCCCCBC

2/1
2/1
4/1

1
6 2
CC
CC
CC
CC
CC
CC

6/1

1
6 3
CBC
CBC
CBC
CBC
CBC
CBC

4/1

提示

• $1\le T\le 10^3$；
• $1\le n,m\le 10^3$；
• $\sum nm\le 10^6$。