Ilker has a passion for becoming an aspiring driver and dreams of winning his first ever race. To achieve this, he needs to calculate the best path in a given racing track, which is represented as a 2D grid. Ilker believes that he will only win the race if he turns a minimal number of times, which means that he should drive as straight as possible.

The racing track's layout can be represented as a grid of \(\mathbf{N}\times\mathbf{M}\) cells, where each cell has one of the following characters:

• .: A cell inside the racing track.
• #: A cell that is unusable and cannot be driven on.
• S: The starting point of the race.
• E: The endpoint of the race.

• Ilker can drive in all eight directions (up, down, left, right, and diagonals) from any given cell. However, he should make sure to minimize the number of 45 degree turns he makes.
• Each 45-degree turn is considered as 1 turn. For example, turning 90 degrees will be considered as 2 turns, e.g. from north to west.

Your task is to help Ilker find the best path by calculating the minimal number of turns he needs to make to reach the endpoint. If it is impossible to reach the endpoint, print \(-1\).

• The borders of the grid are guaranteed to have # characters.
• The racing car will always start pointing up north.

Input

The first line contains \(\mathbf{N}\) and \(\mathbf{M}\), where \(\mathbf{N}\) is the row count and \(\mathbf{M}\) is the column count of the grid.

The next \(\mathbf{N}\) lines each contain a string of \(\mathbf{M}\) characters representing the racing track's grid.

• \(\mathbf{N},\mathbf{M} \leq 1000\)

Output

Print a single integer - the minimum number of 45 degree turns İlker needs to make to reach the endpoint. If it is impossible to reach the endpoint, print \(-1\).

Example

Input 1:

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

Output 1:

7

Input 2:

8 6
######
##.###
#.#.##
#S##.#
####.#
#E##.#
##..##
######

Output 2:

7

Input 3:

3 7
#######
#S.#.E#
#######

Output 3:

-1

Explanation

Input 1: The car starts pointing to the north but immediately turns 45 degrees to the left in cell (3, 2). Afterwards, it turns right 90 degrees in cell (2, 1). Then, turns 45 degrees to the right in cells (1, 2) and (1, 4). Then İlker finishes the race by turning 90 degrees again to the right in cell (2, 5), reaching the endpoint in (3, 4). The amount of 45 degree turns is 7. This optimal solution includes cells (3, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 5), (3, 4). Here's an illustration depicting this scenario:

Input 2: The racecar will start pointing to the north. It will first turn right 45 degrees, and then 90 degrees. It will continue to turn 45 degrees 4 more times, arriving at the endpoint. Total amount turned is (45+90+4*45)/45 = 7 times.

Input 3: The track isn't complete starting from S and ending at E, so there's no way to finish the race.