Dino đã luyện tập nhiều tuần cho một cuộc thi giao hàng. Trong cuộc thi này, người chiến thắng là người chuyển toàn bộ kiện hàng từ kho tới các điểm đến được chỉ định nhanh nhất. Đáng tiếc là Dino chỉ có ~2~ tay, nên tại mọi thời điểm cậu chỉ có thể mang theo nhiều nhất ~2~ kiện hàng.

Dino có thể đặt xuống rồi nhặt lại các kiện hàng theo bất kỳ cách nào, miễn là số kiện đang mang không vượt quá ~2~. Cậu cũng có thể giao hàng theo bất kỳ thứ tự nào, và mỗi kiện hàng có thể được giao tới bất kỳ điểm đến nào. Khi hoàn thành lộ trình, tại mỗi trong ~k~ điểm đến phải có đúng một kiện hàng.

Sân thi đấu là một lưới gồm ~n~ hàng và ~m~ cột. Các ô trống được đánh dấu bằng ~\texttt{.}~, chướng ngại vật bằng ~\texttt{\#}~, ô xuất phát của Dino đồng thời là nơi đặt các kiện hàng được đánh dấu bằng ~\texttt{S}~, còn các điểm giao hàng được đánh dấu bằng ~\texttt{X}~.

Trong ~1~ giây, Dino có thể di chuyển sang một ô kề cạnh theo ~4~ hướng lên, xuống, trái, phải, miễn là ô đó không phải chướng ngại vật. Việc nhặt và đặt kiện hàng không tốn thời gian.

Hãy xác định số giây nhỏ nhất để Dino giao đủ hàng tới mọi điểm đến rồi quay lại ô xuất phát. Nếu không thể, in ra ~-1~.

Input

Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~, với ~1 \le n, m \le 500~ và ~1 \le k \le 67~.

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

Ký tự ~\texttt{X}~ xuất hiện đúng ~k~ lần trong ma trận.

Output

In ra trên dòng duy nhất một số nguyên: số giây nhỏ nhất cần thiết để Dino giao đủ hàng và quay về ô xuất phát, hoặc ~-1~ nếu không thể.

Chấm điểm

• Subtask ~1~ (~17~ điểm): ~k = 2~
• Subtask ~2~ (~26~ điểm): ~k \le 16~
• Subtask ~3~ (~29~ điểm): ~k \le 22~
• Subtask ~4~ (~38~ điểm): Không có ràng buộc bổ sung.

Sample Input ~1~

5 5 3
X...X
.....
.....
.....
S...X

Sample Output ~1~

24

Sample Input ~2~

5 5 4
..X..
#X#..
#...X
.SX#.
.....

Sample Output ~2~

16

Giải thích

• Ví dụ ~1~: Dino sẽ mang ~1~ kiện hàng tới đích ở góc dưới bên phải, đặt nó xuống rồi quay về ô ~\texttt{S}~. Sau đó cậu mang ~2~ kiện còn lại và lần lượt đi qua đích ở góc trên bên phải rồi góc trên bên trái. Cuối cùng Dino quay về vị trí xuất phát, tổng thời gian là ~24~ giây.