#1593 MazeWanderingEasy

55  1 s   128 MB  

Description

According to research conducted recently, listening to classical music increases one's mental abilities, while listening to metal decreases them. Now, yet another experiment is being conducted to try to prove or disprove this statement.
In this new experiment, a mouse is placed in a rectangular maze consisting of NxM squares. Each square either contains a wall or is empty. The maze is structured in such a way that for any two empty squares, there exists exactly one path between them. A path is a sequence of pairwise distinct empty squares such that every two consecutive squares are neighboring. Two squares are considered neighboring if they share a common edge.
One of the empty squares in the maze contains a piece of cheese. The mouse's goal is to reach that square without visiting the same square twice. The mouse can only move between neighboring squares. Since the mouse has been listening to classical music for a week, he is extremely intelligent and guaranteed to achieve his goal.
As the mouse moves from his starting point to the cheese, he may encounter some squares where he must choose between several neighboring squares to continue. This happens when the mouse steps into a square which has more than one neighboring empty square, excluding the square from which he came, or when he has more than one neighboring empty square at the start. These situations are called "decisions" and the mouse will always make the right choice.
You are given a two-dimensional array of characters representing the maze. Empty squares are denoted by '.', walls are denoted by uppercase 'X', the mouse's starting point is denoted by 'M', and the square containing the cheese is denoted by '*'. Find the number of decisions the mouse will make on his way to the cheese.

Input

The first line of the input gives a number of test cases, T.
The first line of each case gives the number of rows R (1 <= R <= 50) and columns of the map C (1 <= C <= 50).
Next R line gives the map each containing C characters of the corresponding row of the map.

Output

For each test case, output the minimum number of decisions on each line.

Sample Input

Sample Output

3
1 3
*.M
2 3
*.M
.X.
3 3
...
XMX
..*
0
1
2