Phá tường thoát ra

Một robot bị kẹt trong một bản đồ $n$ hàng, $m$ cột. Ô # là tường, ô . là ô trống, robot đứng ở ô S (ô trống). Mỗi bước robot đi sang một ô chung cạnh (lên, xuống, trái, phải). Robot có thể đi vào ô tường, nhưng trước đó phải phá bức tường ấy; tường đã phá thì trở thành ô trống.

Robot thoát được khi nó đứng ở một ô thuộc mép bản đồ (hàng đầu, hàng cuối, cột đầu hoặc cột cuối), vì từ đó chỉ cần bước thêm một bước là ra ngoài.

Hãy tính số bức tường ít nhất robot phải phá để thoát ra.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,m$.
• $n$ dòng tiếp theo, mỗi dòng là một xâu độ dài $m$ gồm các ký tự ., #, S. Có đúng một ký tự S.

Dữ liệu ra

In một số nguyên: số bức tường ít nhất cần phá.

Ràng buộc

• $1\le n,m\le 1000$

Ví dụ