Andy loves playing Minecraft. Recently, he has been very interested in how Minecraft path-finding works. He built a two-dimensional maze out of bedrock, and wanted to test how zombies would path-find through the maze. Wanting to implement a similar algorithm for himself, but not knowing how to, he asks you to implement the algorithm for him!

Recall that Minecraft's path-finding algorithm first tries to find the shortest length path in blocks. Then, it tries to find a valid path of that length. Because there may be multiple paths of the shortest length, Andy only wants you to print the shortest length.

Note that the zombie can only travel horizontally and vertically. It cannot travel diagonally.

Input Specification

The first line will contain one integer, ~N~ ~(2 \le N \le 500)~, indicating that the maze is an ~N \times N~ grid of blocks.

The next ~N~ lines will each contain ~N~ characters, ~c_{i,j}~, the two-dimensional maze that Andy built.

It is guaranteed that ~c_{i,j}~ will only be one of the following characters:

• # means there is a bedrock block there, and that the zombie cannot go through.
• . means there is nothing there, and the zombie can go through.
• S means the starting location of the zombie. It is guaranteed that S will only appear exactly once.
• E means the location the zombie wants to go to. It is guaranteed that E will only appear exactly once.

Output Specification

Output the minimum length of a path from the S to the E. If there is no path, print There is no path, Andy!.

Sample Input 1

5
#....
#.##.
#E.#.
.#.#.
.#..S

Sample Output 1

5

Sample Input 2

4
####
#S..
#..#
###E

Sample Output 2

There is no path, Andy!