Quân mã

Một bàn cờ có $n$ hàng và $n$ cột, hàng đánh số từ $1$ đến $n$ từ trên xuống, cột đánh số từ $1$ đến $n$ từ trái sang. Mỗi ô là ô trống (.) hoặc ô cấm (#).

Một quân mã đứng ở ô $(r_1,c_1)$ và cần đi tới ô $(r_2,c_2)$. Mỗi nước, quân mã đi từ ô $(r,c)$ tới một trong $8$ ô $(r\pm 1,c\pm 2)$ hoặc $(r\pm 2,c\pm 1)$, với điều kiện ô đó nằm trong bàn cờ và là ô trống. Quân mã nhảy qua các ô ở giữa, nên các ô cấm nằm giữa không cản đường.

Hãy tính số nước đi ít nhất để quân mã tới ô đích, hoặc cho biết không thể tới được.

Dữ liệu vào

• Dòng đầu tiên chứa năm số nguyên $n$, $r_1$, $c_1$, $r_2$, $c_2$.
• $n$ dòng tiếp theo, mỗi dòng là một xâu độ dài $n$ gồm các ký tự . và # mô tả một hàng của bàn cờ.

Dữ liệu bảo đảm ô $(r_1,c_1)$ và ô $(r_2,c_2)$ là ô trống.

Dữ liệu ra

In ra số nước đi ít nhất, hoặc $-1$ nếu quân mã không thể tới ô đích.

Ràng buộc

• $1\le n\le 400$
• $1\le r_1,c_1,r_2,c_2\le n$

Ví dụ