Nữ hoàng Sofia bị mắc kẹt trên một bàn cờ bí ẩn có ~n~ hàng và ~m~ cột. Trên bàn cờ có ô xuất phát của bà, ký hiệu ~\texttt{S}~, và ô thoát ra ngoài, ký hiệu ~\texttt{E}~. Đáng tiếc là con đường tới lối thoát không hề dễ dàng: một số ô bị chặn, ký hiệu ~\texttt{\#}~, còn các ô trống được ký hiệu ~\texttt{.}~.

Bàn cờ còn chứa những cổng dịch chuyển ma thuật. Một vài chữ số từ ~1~ đến ~9~ xuất hiện đúng ~2~ lần trên bàn cờ. Nếu nữ hoàng đáp xuống một ô chứa chữ số, bà có thể dịch chuyển ngay tới ô còn lại mang cùng chữ số đó mà không tốn thêm lượt di chuyển nào cho việc đi qua cổng. Tuy nhiên, sau khi dịch chuyển, bà không thể tiếp tục đi tiếp theo cùng hướng mà không tốn thêm ~1~ lượt nữa.

Nữ hoàng di chuyển như quân hậu trong cờ vua: trong ~1~ lượt, bà có thể nhảy tới bất kỳ ô nào cùng hàng, cùng cột hoặc cùng đường chéo, miễn là trên đoạn di chuyển đó không có ô bị chặn nào.

Hãy tìm số lượt di chuyển nhỏ nhất để nữ hoàng đi từ ~\texttt{S}~ tới ~\texttt{E}~, hoặc in ra ~-1~ nếu điều đó là không thể.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~, với ~1 \le n, m \le 1000~.

~n~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự ~c_{ij}~ mô tả bàn cờ. Mỗi ký tự là một trong các giá trị ~\texttt{S}~, ~\texttt{E}~, một chữ số từ ~1~ đến ~9~, ~\texttt{.}~, hoặc ~\texttt{\#}~.

Output

In ra trên dòng duy nhất một số nguyên: số lượt di chuyển nhỏ nhất để nữ hoàng tới ô thoát.

Chấm điểm

• Subtask ~1~ (~24~ điểm): ~n, m \le 5~
• Subtask ~2~ (~32~ điểm): Trên bàn cờ không có cổng dịch chuyển.
• Subtask ~3~ (~18~ điểm): ~n, m \le 500~
• Subtask ~4~ (~36~ điểm): Không có ràng buộc bổ sung.

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

Giải thích

• Ví dụ ~3~: Ở lượt đầu tiên, nữ hoàng đi tới ô chứa số ~1~ ở hàng ~1~. Nước đi này hợp lệ vì giữa ~\texttt{S}~ và ô đó không có ô bị chặn. Sau đó bà dịch chuyển tới ô ~1~ còn lại trên bàn cờ, rồi thực hiện thêm ~3~ lượt nữa để tới ô ~\texttt{E}~. Tổng cộng cần ~4~ lượt, và đó là ít nhất.