A bunny 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 carrot. The bunny's goal is to reach that square without visiting the same square twice. The bunny can only move between neighboring squares. Since he has been listening to classical music for a week, he is extremely intelligent and guaranteed to achieve his goal. As the bunny moves from his starting point to the carrot, he may encounter some squares where he must choose between several neighboring squares to continue. This happens when the bunny 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 bunny will always make the right choice. You need to find the number of decisions the bunny will make on his way to the carrot.

Input

The first line contains T <= 150 - The number of test cases. Each test case starts with 2 integers N <= 50 and M <= 50 in the first line. Then follow N lines each containing M characters depicting the NxM maze. Empty squares are denoted by '.', walls are denoted by uppercase 'X', the bunny's starting point is denoted by 'M', and the square containing the carrot is denoted by '*'. Each row of maze will be of the same length ie M. It is gauranteed that the maze will contain only '.', 'X', 'M' or '*' characters. There will be exactly one '*' character in maze. There will be exactly one 'M' character in maze. Also, for every pair of empty squares in the maze, there will exist exactly one path between them.

Output

For each test case, print the number of decisions the bunny will make on his way to the carrot on a single line.

Example

Input:
2
4 11
2
4 11
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
3 3
...
XMX
..*
.X.X......X
.X*.X.XXX.X
3 3
...
XMX
..
Output:
3
2
Explanation of 2nd input : The bunny has to take 1st decision at
start point as it is adjacent to 2 empty cells, and 2nd decision
at the cell just before the goal.