Vua Arthur và các hiệp sĩ bàn tròn thường gặp nhau vào đầu năm mới để ăn mừng tình bạn của họ. Để tưởng nhớ sự kiện này, chúng ta xem xét một trò chơi, trong đó có một quân vua và một vài quân mã được đặt ngẫu nhiên trên các ô riêng biệt. Bàn cờ có kích thước \(n × n\), trên bàn cờ có một số ô cấm những ô còn lại là những ô tự do – ô có thể di chuyển vào được. Các ô đặt quân mã và quân vua đang đứng ở các ô tự do.

Tại mỗi bước tất cả các quân đều phải di chuyển theo quy tắc và không được đi vào ô cấm, hãy tìm cách di chuyển để chúng gặp nhau nhanh nhất.

Input

• Dòng đầu là số \(n\);
• \(n\) dòng tiếp theo, mỗi dòng 1 xâu \(n\) ký tự, gồm các ký tự . thể hiện ô trống, # thể hiện ô cấm không được phép đi vào, T thể hiện vị trí vua đang đứng, M thể hiện vị trí quân mã đang đứng.

Output

• Gồm một số là số bước ít nhất để các quân gặp nhau, nếu không thể gặp được nhau ghi \(-1\).

Scoring

• Subtask \(1\): \(n ≤ 20\) và chỉ có một quân mã;
• Subtask \(2\): \(n ≤ 100\) và chỉ có một quân mã;
• Subtask \(3\): \(n ≤ 100\).

Example

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

2