고질라

고질라가 다시 도쿄를 짓밟고 있다. 다행히 최정예 방위 메크 부대(SDMF)가 공격을 막으려고 메크 유닛을 출동시켰다. 메크 유닛은 이족 보행 거대 로봇이고, 보통 일본 십 대 소년이 조종하며, 초강력 무기를 싣고 있다. 이 무기는 한 발만 맞혀도 고질라를 제압한다.

SDMF에는 제약이 두 가지 있다. 첫째, 메크 유닛은 몸집이 너무 커서 주거 구역을 밟고 지나갈 수 없다. 밟으면 도쿄 시민을 깔아뭉갠다. 둘째, 무기의 위력이 너무 세서 발사하는 메크와 고질라 사이에 주거 구역이 하나라도 있으면 조종사가 발사할 수 없다.

SDMF는 고질라와 맞붙기 전에 모의 실험을 몇 번 돌리려 한다. 실험은 고질라가 날뛰는 도쿄 지역을 나타낸 2차원 지도 위에서 진행한다. 시간은 라운드 단위로 흐르고, 한 라운드는 두 턴으로 나뉜다. 첫 번째 턴에는 고질라가 한 번 움직이고, 두 번째 턴에는 메크 유닛이 한 번 움직인다. 한 번의 이동은 북, 동, 남, 서 중 한 방향으로 한 칸 옮겨 가는 것이다.

고질라는 머리가 나빠서 움직임이 훤히 예측된다. 우선 고질라는 이미 방문한 칸으로는 다시 들어가지 않는다. 매 라운드 첫 번째 턴에 고질라는 다음과 같이 행동한다.

• 인접한 칸에 부술 집이 있는지 살핀다. 인접한 칸이 주거 구역이면 그 칸으로 이동해 구역을 부순다. 부서진 주거 구역은 폐허 구역이 된다. 고질라는 북, 동, 남, 서 순서로 살핀다. 먼저 북쪽을 보아 주거 구역이 있으면 그리로 이동하고, 없으면 동쪽에 부술 주거 구역이 있는지 보는 식이다.
• 인접한 칸에 주거 구역이 하나도 없으면 북쪽으로 이동하려 한다. 그 이동이 지도 밖으로 나가거나 이미 방문한 칸으로 들어가는 것이면 대신 동쪽으로 이동하려 한다. 동쪽으로 갈 수 없으면 남쪽으로 이동하고, 남쪽으로도 갈 수 없으면 서쪽으로 이동한다. 메크가 버티고 서 있어도 고질라는 개의치 않고 그 칸으로 들어간다. 이때 고질라는 다음 턴에 그 메크 유닛의 사정거리 안에 있는 것으로 본다.
• 갈 수 있는 칸이 하나도 없으면 고질라는 제자리에서 포효하며 팔을 휘두르고, 도쿄에는 아무 피해도 주지 않는다.

매 라운드 두 번째 턴에 각 메크 유닛은 제자리에 머무르거나, 인접한 비주거 구역이나 폐허 구역으로 이동할 수 있다. 지도 밖으로는 나갈 수 없다. 이동할 때는 북, 동, 남, 서 중 한 방향으로 한 칸 움직인다. 다른 메크 유닛이 있는 칸으로도 이동할 수 있다. 메크와 고질라 사이에 가로나 세로 직선이 놓이고 그 선 위에 주거 구역이 하나도 없으면 메크는 무기를 발사할 수 있다. 발사할 수 있게 된 메크는 그 턴에 바로 쏜다. 한 턴에 이동과 발사를 모두 할 수 있다.

한 라운드 첫 번째 턴에 부서진 주거 구역은 같은 라운드에 메크가 발사하더라도 개수에 들어간다.

고질라가 날뛰는 도쿄 지역의 지도와 메크의 시작 위치가 주어진다. 메크 유닛이 고질라를 제압할 때까지 부서지는 주거 구역 수의 최솟값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

• 첫 줄에 지도의 길이 $L$과 너비 $W$가 공백을 사이에 두고 주어진다. ($3 \le L \le 1000$, $3 \le W \le 1000$)
• 다음 $W$개 줄에 각각 $L$개의 문자가 주어져 도쿄 지도를 나타낸다. 문자의 뜻은 다음과 같다.
  • '.': 비주거 구역
  • 'R': 주거 구역
  • 'G': 고질라의 시작 위치. 이 칸은 항상 비주거 구역이다.
  • 'M': 메크 유닛의 시작 위치. 이 칸은 항상 비주거 구역이다.

지도의 왼쪽 위 칸이 도쿄의 북서쪽 끝이고, 오른쪽 아래 칸이 남동쪽 끝이다.

한 실험에 나오는 메크 유닛은 최대 100대다.

고질라는 항상 어떤 메크 유닛에게 제압될 수 있다.

각 테스트 케이스마다 메크 유닛이 고질라를 제압할 때까지 부서지는 주거 구역 수의 최솟값을 한 줄에 하나씩 출력한다.