Ở tuổi xế chiều, sau bao thăng trầm với nghề kinh doanh và hoạt động thiện nguyện, Tuấn tìm thấy sự bình yên bên bàn cờ vua, cũng là niềm đam mê mà anh theo đuổi từ nhỏ. Trong suốt những năm tháng chơi cờ và giảng dạy, Tuấn đã dày công thiết kế một thế cờ huyền thoại, một thử thách tư duy mà chưa một học trò nào có thể phá giải.

Tuấn mô phỏng thế cờ đó dưới dạng một bàn cờ vuông ~n \times n~. Trên bàn cờ có một quân vua, các quân mã và các ô cấm. Tại mỗi lượt, tất cả các quân đều phải di chuyển theo quy tắc và không được phép di chuyển vào ô cấm tuy nhiên chúng có thể đứng trên cùng một ô. (Quân vua có thể di chuyển trong ~8~ ô kề cạnh, quân mã có thể di chuyển một bước theo mình chữ ~L~ quen thuộc).

Yêu cầu: Hãy xác định số lượt di chuyển ít nhất để tất cả các quân (bao gồm cả vua và các quân mã) cùng hội tụ tại một ô trống hợp lệ, tại cùng thời điểm.

Input

• Dòng 1: chứa số nguyên ~n~ ~(1 \le n \le 100)~ là kích thước bàn cờ;

• ~n~ dòng tiếp theo: mỗi dòng gồm ~n~ ký tự bao gồm các ký tự '.' thể hiện ô trống có thể đi vào, '#' thể hiện ô cấm, 'T' thể hiện vị trí ban đầu của quân vua, 'M' thể hiện vị trí ban đầu của các quân mã.

Output

Ghi một số nguyên duy nhất là số lượt di chuyển ít nhất để tất cả các quân gặp nhau tại một ô hợp lệ, hoặc in ra ~-1~ nếu không thể.

Scoring

Nếu học sinh chỉ in kết quả ~-1~ trong tất cả các test thì không được điểm của bài toán.

Sample Input 1

5
M....
.....
.#...
.#..#
...#T

Sample Output 1

2

Notes

Quân mã có thể đi theo lộ trình ~(0,0) \rightarrow (1,2) \rightarrow (2,4)~, còn vua từ ~(4,4) \rightarrow (3,3) \rightarrow (2,4)~. Vì các quân cùng đến ô ~(2,4)~ tại lượt thứ ~2~, kết quả là ~2~.