Background

王学长最喜欢冒险了，现在他被黑衣人关在迷宫现在你可以操纵王学长上下左右，如果能找到出口输出移动的最小步数，找不到输出“呜呜呜”。

Description

输入N表示正方形迷宫长宽

1表示障碍物，0表示可通行，w表示王校长，q表示出口。

输入迷宫
1 0 1 0
w 0 1 0
0 0 0 1
0 0 q 1

Format

Input

2<=N<=10

Output

如果能找到输出最小步数sum找不到输出呜呜呜

Sample 1

Input

4
1 0 1 0
w 0 1 0
0 0 0 1
0 0 q 1

Output

4

Sample 2

Input

4
1 0 1 0
w 0 1 0
0 1 0 1
0 1 q 1

Output

呜呜呜

Limitation

1s, 1024KiB for each test case.

Source

Vijos Original