배고픈 가가멜

마법사 가가멜은 배가 고파서 각 칸이 검은색 또는 흰색인 $N$행 $M$열 격자 안에서 먹을 것을 찾으려 한다.

가가멜은 왼쪽 위 칸에서 출발해 체바피가 있는 오른쪽 아래 칸으로 가려 한다. 왼쪽 위 칸과 오른쪽 아래 칸은 항상 검은색이다.

매 단계마다 가가멜은 위, 아래, 왼쪽, 오른쪽 중 한 방향의 인접한 칸으로 반드시 이동해야 한다. 이동한 칸이 흰색이면 다음 일이 일어난다. 격자의 모든 흰색 칸 중 하나를 같은 확률로 무작위로 골라, 가가멜이 그 칸으로 순간이동한다. 현재 있는 칸이 골라질 수도 있다.

그다음 단계로 넘어간다. 즉 각 단계에서 가가멜은 먼저 인접한 칸으로 이동하고, 그 칸이 흰색이면 최대 한 번 순간이동이 일어난다.

가가멜의 먹을 것 찾기는 오른쪽 아래 칸에 도착하는 순간 끝난다.

가가멜이 최적으로 움직인다고 할 때, 오른쪽 아래 칸에 도착할 때까지 걸리는 걸음 수의 기댓값을 구하라.

첫 줄에 자연수 $T$($1 ≤ T ≤ 1000$)가 주어진다. 이는 답해야 할 시나리오의 수이다.

각 시나리오의 첫 줄에는 자연수 $N$과 $M$($1 ≤ N, M ≤ 1000$)이 주어진다. 이어서 $N$개의 줄에 걸쳐 격자의 각 행이 $M$개의 문자로 주어진다. 문자 'C'는 검은 칸, 'B'는 흰 칸을 뜻한다.

모든 시나리오의 칸 수를 합한 값은 $10^6$을 넘지 않는다.

각 시나리오에 대해 기댓값을 기약분수 꼴로 출력한다.

첫 번째 시나리오에서는 모든 칸이 검은색이므로 오른쪽 아래 칸으로 곧장 가는 것이 최적이다. 두 번째 시나리오에는 흰 칸이 두 개 있지만, 순간이동 후 어느 칸에 도착하든 다음 단계에서 오른쪽 아래 칸으로 갈 수 있다.