Queen Sofia is trapped on a mysterious chessboard of ~n~ rows and ~m~ columns. The board contains her starting square (labeled S) and her exit square (labeled E). Unfortunately, the path to the exit is not easy - some squares are blocked (labeled #), while others are free (labeled .).

But the board also hides magical portals! Some of the numbers between ~1~ and ~9~ appear exactly twice on the board. If the queen lands on a square with a number, she can teleport to another square on the board with the same number without spending extra moves to move through the portal. The queen cannot continue moving in the same direction after passing through the portal without an additional cost of ~1~ move.

The queen can move in a chess-like manner - in one move she can jump to any square that is on the same diagonal, row, or column as her, but only if there are no blocked squares between her and that square (including the starting and ending squares of the move).

Find and print the smallest number of moves required for the queen to reach the exit square from the starting square, or print -1 if this is not possible.

Input Specification

The first line contains the integers ~n~ and ~m~ ~(1 \le n, m \le 1\,000)~, the number of rows and the number of columns of the board.

Each of the next ~n~ lines contains ~m~ characters ~c_{ij}~, the description of the board. Each character of the board will be one of S, E, a number between ~1~ and ~9~, . or #.

Output Specification

In the first and only line, print a single number - the smallest number of moves required for the queen to reach the exit square.

Constraints

Subtask	Points	Constraints
~1~	~24~	~n, m \le 5~
~2~	~32~	There won't be any portals on the board.
~3~	~18~	~n, m \le 500~
~4~	~36~	No additional constraints.

Sample Input 1

4 4
S..1
####
1.#E
....

Sample Output 1

4

Sample Input 2

3 3
S..
.#.
..E

Sample Output 2

2

Sample Input 3

5 4
S.21
####
2##1
###.
E..#

Sample Output 3

4

Explanation for Sample Output 3

Queen Sofia will move to number 1 in the ~1~st row in her first move (note that there is no blocked square between S and 1, so this move is indeed possible). She will then teleport to the second number 1 in the matrix and will make ~3~ more moves to the exit square. With these moves, she has indeed made the fewest number of moves needed from the starting to the exit square.