Mummy Maze

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Mummy Maze is one of my favourite games of Fantasy Games series. In the game you, a fearless explorer, are located in a treacherous chamber of an Egyptian pyramid. The pyramid is riddled with traps, infested with deadly scorpions, and haunted by relentless mummies. There is only one exit in the chamber where you can get away. Your objective is to get to the exit without getting caught by the scorpions or mummies, and finally claim the treasure waiting at the top of the pyramid.

Let's consider a simplified game mode following.

Scene and Roles

  • A maze of N * N squares is given. Some walls exist obstructing some pairs of adjacent squares. The borders of the maze are also closed walls except a gap which is the only one exit.
  • A gate may exist obstructing two adjacent squares in the maze. If there is a gate, the maze will also have a key on a certain square. Gate is never located at the border.
  • You, the explorer, are located on one square of the maze at the initial situation.
  • There are one or two mummies located on other squares different from your starting point at the initial situation.

Movements

  • In each turn, you, the explorer, can move to a directly adjacent square (no wall obstructing). Diagonal moves are not allowed. You can also choose to pass this turn so that the explorer will stay there without movement.
  • Aftar your turn, it is the mummies' turn. A mummy can move twice at most. For each move, if the mummy can move horizontally and get closer to you, it will do so. If the mummy can't move horizontally, but can move vertically and get closer to you, it will do that instead. Otherwise, it will stay there for this turn. Mummies move simultaneously.
  • Two mummies may move to the same place. Then they will turn into only one mummy. (or say that one of them is lost, which one lost is insignificant)

Gate and Key

  • The gate is closed at the initial situation.
  • The gate can be opened or closed immediately by moving onto the key square. The key can be triggered either by you or a mummy.
  • If two mummies step on the key simultaneously, the key is triggered twice.

Goal

  • If you and a mummy are located on the same square, then you are caught.
  • Your objective is to get away the maze from the exit at the border without getting caught by the mummies.

Now is your task. What is the minimum number of turns you need to flee the maze?

Input

Input contains multiple test cases. Each test case starts with an integer N (1 <= N <= 10) in one line, which is the size of the maze. Then N * 2 + 1 lines follow, each line consists of N * 2 + 1 characters, which shows the figure of the maze. The characters of odd line and odd column is always '+'. The characters of odd line and even column or of even line and odd column is either '-' or '|' when it specifies a wall, is ' ' when it specifies no wall or an exit at the border, or is 'G' when it specifies a gate. The characters of even line and even column is ' ', 'E', 'M' or 'K' which specifes an empty square, starting poing of the explorer, starting poing of a mummy or a key respectively.

Output

There is one line for each test case, which is the minimum number of turns you need to flee the maze. If you can't get away the maze, just output -1.

Sample Input

3
+-+ +-+
|M |
+ +-+ +
| | |
+ +-+ +
|E |
+-+-+-+
3
+-+ +-+
|M |
+ +-+ +
|M | |
+ +-+ +
|E |
+-+-+-+
3
+-+-+-+
| E |
+ +-+G+
| |K|
+ +-+ +
| |M|
+-+ +-+
3
+-+-+-+
| E |
+ +-+G+
|K | |
+ +-+ +
| |M|
+-+ +-+

Sample Output

7
-1
-1
4
Submit

Source: Online Contest of Fantastic Game