Stuck on videogames P22716

Videogames are an indispensable part of the life of Noldo. So much so, that he can even delay the presentation of the final project of his degree for a good time playing. In this problem you must solve the videogame that Noldo was playing the day he should have been defending his project.

You must traverse a rectangular grid from an initial position to a final position in the shortest possible time. Each square has a room or an obstacle. You cannot pass through obstacles, or leave off the grid. Each room has a single exit door, initially oriented to the north, east, south or west. After each time unit, all doors move 90 degrees clockwise (for example, a door first oriented to the east, will be oriented to the south, then to the west, etcetera). When you are in a room, you can choose to wait for a time unit, or to move to the room adjacent to the exit door, also spending a time unit.

Input

Input begins with the number of test cases. Every case begins with the number of rows $1 \le n \le 500$ and the number of columns $1 \le m \le 500$ of the map. Each of the following $n$ lines contain the $m$ characters of a row, with the following convention:

• ‘I’: initial room, oriented to the north.

• ‘F’: final room.

• ‘X’: square blocked by an obstacle.

• ‘N’: room initially oriented to the north.

• ‘E’: room initially oriented to the east.

• ‘S’: room initially oriented to the south.

• ‘W’: room initially oriented to the west.

Each grid has exactly one ‘I’ and one ‘F’.

Output

For every given map, print the case number, followed by the minimum time required to go from the origin to destination. If it is impossible, tell so. Follow the format of the example.