Description

Melo, as usual, continued to move bricks from the site, or called maze, to earn money. Suddenly the portions of the maze have caught on fire. Unfortunately, he doesn't know where the exits are, please help little Melo escape this maze.

Now You know Melo's location and each square which is on fire. You must to find a safe way to get out of the maze before he gets hurt by fire, and figure out how fast he can do it.

Melo moves at a rate of one square per second, vertically, horizontally(not diagonally).The fire spreads all four directions(up,down,left,right)from each square is on fire. Melo can escape from any boundary of the maze. The fire and Melo cannot pass through walls.

Format

Input

The first line of input contains a single integer $T$, indicate the number of test cases to follow.

The first line of each test case contains the two integers R and C, separated by spaces, with $1 \leq R,C \leq 1000$. The following R lines of the test case each contain one row of the maze. Each of these lines contains exactly C characters, and each of these characters is one of as follow:

• #, a wall.
• . , a passable square.
• M, Melo’s initial position in the maze, which is a passable square.
• X, a square that is on fire.

Output

For each test case, print an integer representing the earliest time Melo can safely escapse the maze in minutes, or a single line containing ‘Oops!’ if Melo cannot exit the maze before the fire reaches him.

Samples

2
4 4
####
#MX#
#..#
#..#
3 3
###
#M.
#.X

3
Oops!

Hint

There will be exactly one M in each test case, and the X may be multiple.