Once little piglet plotted the graph of her town. Now she was amazed to know that there exist only one unique path from her house to her college, but there are many points in that path where she has to choose between 2 or more paths. Of course one path goes to the college and other one will lead her to a blocked end. You are given a graph she plotted in the form of a NM grid. Each cell of the grid is either ‘.’ , '’,'M’or ‘X’. Where ‘.’ is empty cell and she can walk through it. ‘*’ is the position of her college. ‘M’ is her house’s location and ‘X’ is the blocked cell which she can’t pass. From each cell she can go to any of its 4 neighbouring cell which are not blocked i.e. if she is in (x,y) she can move to (x+1,y),(x-1,y),(x,y-1) or (x,y+1). Now your task is to find the number of decisions she has to make in order to reach college from her house.
Input
First line of input contains a number T i.e. the number of test cases. First line of each test case contains two integers N and M. Next N lines contains a string with only ‘.’, ‘*’, ‘M’ or ‘X’ character and length M.
Output
Your code should print T lines each having one numbers, i.e. the number of decisions she has to make in order to reach her college from her house.
Constraints-
1<=T<=100
1<=N,M<=50
Time limit-
1 second
Sample Input
2
3 3
…
XMX
…*
2 3
*.M
.X.
Sample Output
2
1
Explanation
In the first test case, her starting location is (1,1) i.e. row 1 column 1, now from
there she can either move to (0,1) or (2,1) so it’s the first decision she made.
Now when she reached point (2,1) she can either move to (2,2) or (2,0 )
and it’s the second decision which she has to make.