P1041 The Maze Tokens

Problem Background

https://www.bilibili.com/video/BV1Zx41177W3
This is a BGA(You can understand it as "MV"), and it's This is the source（来源） of my inspiration （灵感）

Problem Statement

AppOfficer is trapped in the maze by Cui2010! He wants to get all the Appofficer's Tokens! He's so evil! Luckily, AppOfficer is able to escape. Now AppOfficer is trapped at the grid A. The exit is at the grid E.The evil Cui2010 has put some mines（地雷）(#) in some parts of the maze so AppOfficer MUST NOT go to these grids! Otherwise it must be a .. And here's the way AppOfficer moves. For example, when he is in \((x,y)\), he can reach \((x+1,y+1)\), \((x+1,y-1)\), \((x-1,y-1)\), \((x-1,y+1)\) in 0 second. But he has to spend 1 second reaching \((x+1,y)\), \((x,y-1)\), \((x-1,y)\), \((x,y+1)\).
The maze is going to collapse（崩塌） if he doesn't escape it as soon as possible! So please tell AppOfficer how many seconds he needs to escape.If he cannot escape anyway, print Czy you don't have force morality! Rat tail juice!.

Input

The first line contains an integer \(n\).
Next \(n\) lines, every line contains \(n\) n characters. That's the discription of the maze.

Output

print how many seconds he needs to escape. Otherwise , print Czy you don't have force morality! Rat tail juice!.

Constraints

• \( 1 \le n \le 2000 \)

Samples

Input 1

3
E # A
. # .
. . .

Output 1

2

• When AppOfficer is taking the first step and the last step, he should spend a second. So the answer is 2.

• Note the space in each line between characters.

Input 2

3
E # A
. # #
. . .

Output 2

Czy you don't have force morality! Rat tail juice!

• It's obvious that AppOfficer cannot escape the maze.