Câu lạc bộ Robotics của Đại học Công nghiệp Hà Nội đang thử nghiệm một robot tự hành giao bưu phẩm trong khu ký túc xá. Bản đồ khu ký túc xá là một lưới ô vuông gồm ~n~ hàng và ~m~ cột. Mỗi ô được mô tả bằng một ký tự: . là ô trống; # là ô có vật cản (toà nhà, bồn cây, …) mà robot không được đi vào; S là vị trí xuất phát của robot; T là vị trí của người nhận hàng. Trên bản đồ có đúng một ô S và đúng một ô T.

Mỗi bước, robot di chuyển từ ô đang đứng sang một trong bốn ô kề cạnh (trên, dưới, trái, phải), với điều kiện ô đó nằm trong lưới và không phải ô vật cản. Robot không đi chéo được.

Yêu cầu

Hãy tìm số bước ít nhất để robot đi từ ô S đến ô T.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~. Mỗi dòng trong ~n~ dòng tiếp theo chứa đúng ~m~ ký tự liền nhau (không có dấu cách) thuộc tập ., #, S, T, mô tả một hàng của lưới.

Kết quả ra

Ghi ra một số nguyên duy nhất là số bước ít nhất; nếu robot không thể đến được ô T thì ghi ~-1~.

Ràng buộc

~1 \le n, m \le 1000~; ~n \times m \ge 2~.

• Subtask 1 (20% số điểm – test 01–04): không có ô vật cản;
• Subtask 2 (30% số điểm – test 05–10): ~n, m \le 50~;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

3 5
S#...
.#.#T
...#.

Kết quả ra mẫu 1

9

Dữ liệu vào mẫu 2

1 5
S.#.T

Kết quả ra mẫu 2

-1

Giải thích

Ví dụ 1: robot đi xuống ~2~ ô, sang phải ~2~ ô, lên ~2~ ô, sang phải ~2~ ô rồi xuống ~1~ ô – tổng cộng ~9~ bước, và không có đường đi nào ngắn hơn. Ví dụ 2: ô vật cản nằm chắn giữa S và T nên robot không thể đến đích.