Description

A delivery robot delivers packages in a warehouse. The warehouse is an N×M grid, with some cells containing shelves (obstacles). The robot can only move in 4 directions: up, down, left, right. Find the minimum number of moves from start (S) to end (E).

Input

Output

Constraints

• •1 ≤ N, M ≤ 100
• •Start and end always exist
• •Start and end are always different

Examples

5 5
S . . # .
. # . # .
. # . . .
. . # # .
# . . . E

8