Công ty XYZ sử dụng các Robot tự hành (Autonomous Mobile Robot-AMR) để di chuyển hàng hóa trong các kho hàng thông minh. Robot nhận nhiệm vụ lấy các kiện hàng ở nhiều vị trí khác nhau trong kho, sau đó đưa các kiện hàng về trạm xuất hàng để đóng gói và chuyển đến khách hàng. Do giới hạn về tải trọng, Robot không thể mang quá hai kiện hàng trong một chuyến đi. Kho hàng được mô phỏng dưới dạng một lưới hình chữ nhật gồm ~N~ hàng và ~M~ cột, các hàng và cột giao nhau tạo thành ô. Mỗi ô trên lưới biểu diễn một vị trí trong kho: có thể là lối đi, giá kệ, trạm xuất hàng hoặc vị trí đặt một kiện hàng cần lấy. Trong đó, mỗi ô chứa một trong ~4~ ký tự sau:

• S là trạm xuất hàng, nơi Robot xuất phát và kết thúc mọi chuyến đi;

• X là vị trí chứa một kiện hàng cần lấy;

• . là lối đi thông thoáng, Robot có thể di chuyển qua;

• # là vị trí giá kệ hoặc vật cản, Robot không thể đi qua.

Robot luôn xuất phát từ trạm S và di chuyển theo quy tắc:

• Robot chỉ được di chuyển sang một ô kề cạnh theo bốn hướng: lên, xuống, trái và phải;

• Mỗi lần di chuyển sang một ô kề cạnh mất đúng ~1~ giây;

• Robot không được đi vào các ô chứa ký hiệu #.

Nếu giữa hai vị trí có nhiều đường đi, Robot luôn có thể chọn đường đi ngắn nhất. Thời gian di chuyển giữa hai vị trí bằng độ dài đường đi ngắn nhất trên bản đồ kho.

Yêu cầu: Tìm tổng thời gian di chuyển của Robot sao cho toàn bộ các kiện hàng được đưa về trạm xuất hàng trong thời gian ngắn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên ~N~, ~M~ và ~K~ ~(1 \le N, M \le 500, 1 \le K \le 22)~ tương ứng với số dòng, số cột và số kiện hàng.

• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ ký tự mô tả bản đồ kho bằng các ký hiệu S, X, . và # (ký tự S và X được viết hoa).

Output

Ghi ra một số nguyên duy nhất là tổng thời gian nhỏ nhất để Robot vận chuyển toàn bộ các kiện hàng và quay trở lại trạm xuất hàng. Nếu nhiệm vụ không thể hoàn thành thì in -1.

Scoring

Sample Input 1

4 4 2
S##X
....
....
...X

Sample Output 1

14

Notes

Giả sử các dòng đánh số từ ~1~ đến ~4~, cột được đánh số từ ~1~ đến ~4~. Robot đi từ ô ~(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (2,4) \rightarrow (1,4) \rightarrow (2,4) \rightarrow (3,4) \rightarrow (4,4) \rightarrow (4,3) \rightarrow (4,2) \rightarrow (4,1) \rightarrow (3,1) \rightarrow (2,1) \rightarrow (1,1)~.