Alice xây dựng trò chơi trên bàn có kích thước ~m \times n~. Một số ô trên bàn được đánh dấu là ô cấm (là ô không thể di chuyển vào), những ô còn lại là ô tự do (là ô có thể di chuyển vào). Khi bắt đầu chơi, Alice sẽ đặt một số quân mã hoặc quân tốt vào các ô tự do, mỗi ô đặt không quá một quân.

Nhiệm vụ của người chơi là tìm cách di chuyển tất cả các quân về cùng một ô. Độ khó của trò chơi là trên bàn có hỗn hợp nhiều quân và tại mỗi đơn vị thời gian tất cả các quân đều cùng phải di chuyển theo quy tắc (xem hình minh họa bên dưới mô tả quy tắc di chuyển). Trong quá trình di chuyển một ô có thể chứa nhiều quân, các quân có thể đi lại những ô đã đi nhưng không quân nào được đi vào ô cấm.

Yêu cầu: Hãy giúp Alice tính thời gian ít nhất để có thể di chuyển tất cả các quân về cùng một ô.

INPUT

Dòng đầu chứa hai số nguyên dương ~m~, ~n~ (~m \times n \le 2000~).

~m~ dòng tiếp theo, mỗi dòng chứa một xâu gồm ~n~ kí tự, trong đó:

• Kí tự ~.~ thể hiện ô trống (ô tự do),

• Kí tự ~\#~ thể hiện ô cấm (không được phép đi vào),

• Kí tự ~T~ thể hiện vị trí một quân tốt,

• Kí tự ~M~ thể hiện vị trí một quân mã.

OUTPUT

In ra một số ~t~ là thời gian ít nhất để di chuyển các quân về cùng một ô. Nếu không có cách di chuyển thỏa mãn, ghi ~-1~.

SAMPLE INPUT 1

2 5
M..T.
.....

SAMPLE OUTPUT 1

1

Giải thích: Có thể di chuyển các quân về ô ở hàng ~2~, cột ~3~.

SAMPLE INPUT 2

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

SAMPLE OUTPUT 2

-1

Giải thích: Mỗi đơn vị thời gian tất cả các quân đều phải di chuyển nhưng quân mã không thể di chuyển, do đó không tồn tại phương án di chuyển thỏa mãn.

SAMPLE INPUT 3

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

SAMPLE OUTPUT 3

3

Giải thích: Có thể di chuyển các ô về hàng ~4~, cột ~4~.

SUBTASKS