Một bảng vuông có kích thước ~N \times N (2 \leq N \leq 100)~ trong đó có đánh dấu một số ô cấm. Trên bảng vuông có ~K~ quân mã cờ vua đang đứng ở những vị trí nào đó trong bảng vuông ~(1 \leq K \leq 100)~. Cần di chuyển những quân mã này đến ~K~ vị trí tập kết (mỗi quân mã một vị trí). Trong quá trình di chuyển, quân mã không được nhảy đến các ô cấm nhưng có thể nhảy đến ô đã có những quân mã khác đang đứng và các ô trống, một quân mã có thể đi tới bất kì vị trí tập kết nào nếu có đường nhảy.

Ở trạng thái ban đầu ~K~ vị trí xuất phát và ~K~ vị trí tập kết được cho hoàn toàn phân biệt.

Quân mã di chuyển như sau:

Yêu cầu

Xác định cách đi các quân mã sao cho tổng các bước di chuyển của các quân mã là ít nhất.

Dữ liệu vào

• Dòng ~1~: Ghi số ~N (N \leq 100)~;
• ~N~ dòng tiếp theo, dòng ~i~ ghi ~N~ ký tự thể hiện hàng ~i ~ của bảng vuông. Ký tự thứ ~i~ là:
  • .: Thể hiện ô trống;
  • C: Thể hiện ô cấm;
  • S: Thể hiện ô có mã đang đứng;
  • D: Thể hiện ô ở vị trí tập kết.

Kết quả ra

Một số nguyên dương duy nhất là tổng các bước di chuyển ít nhất để đưa hết các quân mã về các vị trí tập kết.

Sample Input

6
C.C..S
...SD.
..C...
..SC..
CC.SDD
C....D

Sample Output

7