Mission Impossible

Time Limit: 1 Second    Memory Limit: 32768 KB

Now a spy is besieged in a maze. He knows that there is a telegraph transmitter in the maze somewhere. So he must get there to use the telegraph transmitter to ask for help.

But the mission is very dangerous, because there are some mines in the map (see the figure above). When the spy steps on it, it will immediately explode and the mission will fail. The spy doesn't know where the mines are, thus he will use his best strategy to get to the destination (he will always go along the shortest path). There may be several shortest paths for the spy to choose, and the probability to choose each path from the start point to the destination is the same.

Now your task is to write a program to find the probability that the spy can get to the telegraph transmitter.

Input

The input file begins with an integer T, indicating the number of test cases. Each test case begins with two integers N, M, indicating the height and width of the maze. (N <= 10, M <= 10) In the following N lines, each line contains M characters describing the map. There is one blank line after each map. Spaces denotes empty square, '#' denotes a wall, 'S' denotes the spy, 'M' denotes a mine, and 'T' denotes the telegraph transmitter. It's guaranteed that the four sides of the map are all walls.

Output

For each maze, first output the number of the test case (`Mission #1:', ` Mission #2:', etc.) in a line of its own.

If it is possible for the spy to get to the telegraph transmitter, print a line containing the probability that the spy can get to the telegraph transmitter, exact to two digit to the right of the decimal point. Adhere to the output format shown in the sample below.

If the spy can't get to the destination, output a line containing the statement `Mission Impossible.'

Output a blank line after each test case.

Sample Input

2
6 10
##########
# M   T  #
#  ###   #
#  ###   #
# S      #
##########

6 10
##########
# M  T   #
#  ###   #
#  ###   #
# S      #
##########

Sample Output

Mission #1:
The probability for the spy to get to the telegraph transmitter is 50.00%.

Mission #2:
Mission Impossible.

Submit

Source: ZOJ Monthly, February 2004