Marcus, a Roman explorer hungry for glory, has ventured deep into the heart of an ancient Egyptian tomb. Blinded by ambition, he shatters the sacred urn at the tomb's altar, and in doing so, awakens the Pharaoh's Curse.

Sand begins pouring from cursed vents embedded in the ceilings and walls, spreading rapidly through the tomb's chambers. The sand is relentless; it seeps through every passage and fills every room from floor to ceiling. Marcus must navigate through the tomb and reach the exit before he is buried alive.

The interior of the tomb can be represented as an ~n \times m~ grid. The grid contains the following characters:

• .: an open chamber, passable by both Marcus and sand.
• #: a stone wall, impassable by both Marcus and sand.
• M: Marcus' starting position (also acts as an open chamber).
• E: the exit (also acts as an open chamber).
• *: a cursed sand vent, where sand originates at time ~t=0~.

At each time ~t = 1,2,3,...~, the sand spreads from every sand-occupied cell to all ~4~ directly adjacent cells, unless blocked by a wall. Then, Marcus moves into one of his ~4~ directly adjacent cells, or stays in the same place. Marcus cannot move into a cell that already has sand in it. Since the sand moves before Marcus every time-step, this includes tiles that have been filled with sand on the same turn.

Find the minimum number of time steps for Marcus to reach cell ~E~, or determine that he won't make it out alive!

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n,m \leq 1000)~ — the number of rows and columns of the grid.

The next ~n~ lines each contain a string of length ~m~, describing a row in the grid.

It is guaranteed that the grid contains exactly one M and exactly one E. The edge of the grid is treated as impassable by Marcus and the sand.

Output

Print a single integer, the minimum number of time steps for Marcus to reach the exit. If it is impossible for Marcus to reach the exit, output -1.

Clarifications

• Since E and M are both open chambers, sand can spread into them. As sand moves before Marcus each time-step, if sand spreads into either the current cell occupied by Marcus, or the exit, it is instantly impossible for Marcus to escape.

Example

Input 1

1 3
*ME

Output 1

-1

Although Marcus starts only 1 tile from the exit, the sand moves first every turn and spreads into his chamber, instantly cooking him before he can move, so it is impossible to escape here.

Input 2

5 5
##*##
#M..#
#...#
#..E#
#####

Output 2

-1

Marcus's only option is to continually move downwards due to the sand spreading to his right, but he will eventually be trapped there before he can reach the exit. We can illustrate this turn-by-turn:

##*##    ##*##    ##*##    ##*##
#M..#    #.*.#    #***#    #***#
#...# -> #M..# -> #.*.# -> #***#
#..E#    #..E#    #M.E#    #M*E#
#####    #####    #####    #####

Remember the sand moves before Marcus each turn, so even though in the above diagram it looks like he could move to the right, he cannot as the sand will occupy those tiles first.

Input 3

5 5
#*...
M....
..#..
.#...
..E..

Output 3

5

Marcus is again forced downwards by the spreading sand, but the convenient wall allows him to then turn to the right and reach the exit before the sand can block him off. We can illustrate this turn by turn.

#*...    #**..    #***.    #****    #****    #****
M....    .*...    ***..    ****.    *****    *****
..#.. -> M.#.. -> .*#.. -> **#.. -> **#*. -> **#**
.#... 1  .#... 2  M#... 3  .#... 4  *#... 5  *#.*.
..E..    ..E..    ..E..    M.E..    .ME..    *.M..

Input 4

1 9
M...E...*

Output 4

-1

Marcus and the sand source are the same distance from the exit. As the sand moves before Marcus, it will reach the exit before him, making escape impossible.

Input 5

6 9
#########
......E##
M#####...
.........
..##..###
*.##..###

Output 5

7

If Marcus goes the bottom route, the sand will cut him off before he can reach the exit. Very suspicious. Luckily, he can take the top route and reach the exit before the sand in 7 steps.

Input 6

3 3
M.#
.#.
#.E

Output 6

-1

It is possible for the escape to be impossible even without sand, just due to the layout of the walls.