Câu chuyện trong buổi tối hôm nay kể về một em mèo mướp tội nghiệp. Vì ghen tị với độ dễ thương của em mèo nên vào một ngày nọ, mụ phù thủy độc ác đã nhốt em vào mê cung hình vuông kích thước ~n \times n~ mà khó tìm được lối thoát. Các vị trí trong mê cung được chia thành các ô vuông, mỗi ô vuông có thể là khoảng trống, hoặc là cạm bẫy. Em mèo được đặt vào một ô nào đó, xung quanh em có thể có toàn là cạm bẫy. Do hoang mang nên em mèo khi bắt đầu chạy thì chỉ biết chạy thẳng theo 1 trong các hướng: trái, phải, lên, xuống chứ không biết rẽ lần nào nữa. Hãy tính xem em mèo có thoát ra được mê cung hay không, với số bước ít nhất là bao nhiêu nhé? Chú ý rằng nếu em mèo đang ở biên của mê cung thì em chỉ cần nhảy thêm ~1~ bước là thoát khỏi, vì mê cung không có tường.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 \le n \le 100.~ Trong các dòng tiếp theo là mô tả cho thông tin các ô trong mê cung, ký hiệu ô trống bởi dấu O còn ô có cạm bẫy là X, chỉ có đúng một ô chứa ký hiệu M, chỉ vị trí của em mèo mướp.

Output

Số bước ngắn nhất để thoát khỏi mê cung nếu chỉ chạy thẳng, hoặc in ra ~-1~ nếu không có cách nào thoát khỏi.

Sample input 1

3
XOX
OMX
OXX

Sample output 1

2

Sample input 2

3
OXO
XMX
OXO

Sample output 2

-1

Sample input 3

4
OOXX
XOMX
OXOX
XXXX

Sample output 3

-1

Giải thích. trong VD1, em mèo có thể đi thẳng lên hoặc đi rẽ sang trái thì đều thoát được; còn trong VD2, xung quanh em đều là cạm bẫy nên không có lối thoát; trong VD3, em mèo dù có một cách thoát nhưng do em phải rẽ ít nhất một lần mới ra được và em cũng không thể thoát.