In the middle of a well planned heist in the bank of Spain, the chief security Gandia fled the hostage situation and got firearms from the panic room well enough to blow up the entire bank. The robbers are now in a horrible situation. They need to find and lock Gandia at any cost. Four of the robbers: Tokyo, Rio, Moscow & Nairobi scattered around the bank guarding specific locations.
Gandia is a tricky one, and he is moving through the ventilator shaft inside the bank to avoid contact with the robbers. His intention is to take them one by one when they are isolated from each other. Gandia also has little time left, so he wants to kill them all as quickly as possible.
Input
First line of input will contain T ≤ 5 the number of test cases, followed by R ≤ 10 & C ≤ 10 the number of row & column. Then there will be a 2d grid, containing following special characters :
- '.' : Empty space
- '#': Blocked space
- 'G': Gandida's location
- 'T': Tokyo's location
- 'R': Rio's location
- 'N': Nairobi's location
- 'M': Moscow's location
Gandia can move to adjacent cell (up, down, left, right, top-right, top-left, bottom-right, bottom-left) from his current cell. Empty spaces means these are accessible to all. Blocked spaces are not accessible from inside the bank except the ventilator shaft. Moving from one cell to another takes 1 minute & killing takes 2 minutes time.
Note: G, T, R, N, M will occur only once in the grid.
Output
Print a line for each case like following (where x is the case number, y is the number of minutes to kill all) :
- Case #x: Time taken y minutes
See the sample for better understanding.
Sample
| Input | Output |
|---|---|
1 5 5 GTRMN ##### ##### ##### ##### | Case #1: Time taken 12 minutes |
First Gandia goes to cell where Tokyo is (takes 1 minute) and kills her (takes another 2 minutes). Then he moves on to kill Rio and so on. Thus total takes 12 minutes. | |
