3D Maze

Problem Description

You are trapped inside a three-dimensional space and must find the shortest path to escape!

• The space is built out of unit cubes.
• Each step to an adjacent cell (up / down / north / south / east / west) takes one minute.
• You may not move diagonally, and all sides are sealed.

Is it possible to escape? If so, how many minutes does it take?

Input Format

There are multiple test cases. One test case describes a single 3D maze:

• The first line of the whole input gives the number of such spaces (mazes).
• The description of each space starts with one line containing $L$, $R$ and $C$ (each $\le 30$).
• $L$ is the height (number of layers) of the space.
• $R$ and $C$ are the number of rows and columns of each layer.
• Then follow $L$ layers of the dungeon, each with $R$ rows of $C$ characters.
• Each character is one cell: # is a wall (impassable), . is an empty cell, S is your starting cell, and E is the exit.
• A blank line separates consecutive layers.

The input ends when $L$, $R$ and $C$ are all $0$.

Output Format

For each space, print one line.

• If you can escape, print:

Escaped in x minute(s).

where $x$ is the minimum number of minutes needed to get out.

• If escape is impossible, print:

Trapped!

These two messages must be printed exactly as shown (one "minute" or more — the s is always present) — the judge compares them character by character.

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!

Constraints

$1 \le L, R, C \le 30$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• This is a 3D BFS. Each cell has up to 6 neighbours instead of 4; the rest of the idea is identical to a plain 2D shortest path.
• Skip the first space (read $L, R, C$); if all three are $0$ you are done.
• Watch the blank line between layers — it is part of the input and your parser must consume it.