Godzilla

Godzilla is rampaging through Tokyo again. The Superior Defender Mech Force (SDMF) has sent its mech units to stop the attack. A mech unit is a gigantic bipedal robot, usually piloted by a Japanese teenager, that carries a weapon of superior destruction. One hit from that weapon neutralizes Godzilla.

The SDMF faces two problems. First, a mech unit is so big that it cannot walk over a residential sector, because it would trample the people of Tokyo. Second, the weapon is so powerful that a pilot cannot fire it at Godzilla while any residential sector lies between the firing mech and Godzilla.

The SDMF wants to run some simulations before it faces the Godzilla threat. A simulation uses a two-dimensional map of the area of Tokyo where Godzilla is running amok. Time passes in rounds, and each round has two turns. On the first turn Godzilla makes a move. On the second turn the mech units make a move. A single move goes one sector North, East, South or West.

Godzilla is lacking in brain matter and his movement is completely predictable. He never moves into a sector he has already visited. On the first turn of each round he acts like this.

• He looks for a house to destroy next to him. If a sector adjacent to him is residential, he moves into that sector and destroys it. A destroyed residential sector becomes a ruined sector. He looks around in the order North, East, South, West. He first looks North to see whether there is a residential sector and moves there if there is. Otherwise he looks East to see whether there is a residential sector to destroy, and so on.
• If no adjacent sector is residential, he tries to move North. If that move would take him outside the map or into a sector he has already visited, he tries to move East instead. If he cannot move East, he moves South. If he cannot move South, he moves West. The terrifying presence of a mech does not stop Godzilla from moving into the sector that mech occupies. In that case he is considered to be in range of that mech unit's weapon of superior destruction on the next turn.
• If he has no move options left, he starts roaring and wails his arms instead, and Tokyo takes no damage.

On the second turn of each round, each mech unit either stays where it is or moves into an adjacent non-residential sector or a ruined sector. It cannot move outside the map. When it moves, it goes one sector North, East, South or West. It may move into the sector of another mech unit. A mech can fire its weapon at Godzilla when there is a straight horizontal or vertical line between the mech and Godzilla and no residential sector obstructs that line. A mech that can fire does so on the same turn, and it may move and fire on that turn.

A residential sector destroyed on the first turn of a round still counts even when a mech fires later in that same round.

Given a map of the Tokyo area where Godzilla is rampaging and the starting positions of the mechs, determine the minimum number of residential sectors that will be destroyed before a mech unit neutralizes Godzilla.

The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

• One line with two space separated integers $L$ and $W$, the length and the width of the map of Tokyo in sectors. ($3 \le L \le 1000$, $3 \le W \le 1000$)
• $W$ lines of $L$ characters each, describing the map of Tokyo. The characters are:
  • '.': a non-residential sector
  • 'R': a residential sector
  • 'G': the starting position of Godzilla. This is always a non-residential sector.
  • 'M': the starting position of a mech unit. This is always a non-residential sector.

The sector in the top left corner of the map is the northwest corner of Tokyo, and the sector in the bottom right corner is the southeast corner.

A simulation contains at most 100 mech units.

It is always possible for Godzilla to be neutralized by a mech unit.

For each test case, print one line containing a single integer, the minimum number of residential sectors that will be destroyed before a mech unit neutralizes Godzilla.