Bessie lại kẹt phía sai của chuồng Farmer John. Mắt kém nên cần giúp đi qua chuồng.

Chuồng là lưới $N \times N$ ô vuông ($2 \leq N \leq 20$), trống hoặc có cỏ khô không đi qua được. Nó đi từ dưới trái $(1,1)$ tới trên phải $N,N$. Lệnh là “tiến”, “quay trái 90 độ”, “quay phải 90 độ”. Cần chuỗi ngắn nhất. Nếu ra ngoài vào tường hay vào cỏ, nó đứng yên và sang lệnh kế.

Không biết lúc đầu hướng lên $(1,2)$ hay phải $(2,1)$. Cho chuỗi ngắn nhất tới đích trong cả hai trường hợp. Tới rồi bỏ qua lệnh sau.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa $N$.

$N$ dòng tiếp mỗi dòng đúng $N$ ký tự. Đầu dòng cuối là $(1,1)$, cuối dòng đầu là $(N,N)$.

H là cỏ khô, E là ô trống.

$(1,1)$ và $N,N$ trống và có đường ô trống từ $(1,1)$ tới $N, N$.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

In một dòng độ dài chuỗi ngắn nhất tới đích dù đầu hướng lên hay phải.

Ví dụ

Dữ liệu vào 1

3
EHE
EEE
EEE

Dữ liệu ra 1

9

Ghi chú

“Tiến, phải, tiến, tiến, trái, tiến, trái, tiến, tiến” tới đích ở cả hai hướng đầu trong ví dụ.

Tác giả bài toán: Brian Dean