Hungry Gargamel

The wizard Gargamel is hungry and hopes to find food inside a grid with $N$ rows and $M$ columns, where each cell is black or white.

Gargamel starts in the top left corner and wants to reach the bottom right corner, where the cevapi are. The top left and bottom right cells are always black.

At each step, Gargamel must move to an adjacent cell: up, down, left, or right. If the cell he moves to is white, the following happens. One of all the white cells in the grid is chosen uniformly at random, and Gargamel teleports to it. This may be the cell he is currently on.

Then the process continues with the next step. So in each step, Gargamel first moves to an adjacent cell, and then at most one teleportation happens (if that cell is white).

Gargamel's search ends as soon as he reaches the bottom right corner.

Assuming Gargamel moves optimally, find the expected number of steps he takes before reaching the bottom right corner.

The first line contains a natural number $T$ ($1 ≤ T ≤ 1000$), the number of scenarios.

Each scenario starts with a line containing natural numbers $N$ and $M$ ($1 ≤ N, M ≤ 1000$). The next $N$ lines each contain $M$ characters, either 'C' for a black cell or 'B' for a white cell, describing one row of the grid.

The total number of cells across all scenarios does not exceed $10^6$.

For each scenario, print the expected value as a fraction in lowest terms.

In the first scenario all cells are black, so the best move is to head straight to the bottom right cell. The second scenario has two white cells, but wherever Gargamel lands after teleporting, he can reach the bottom right cell in the next step.