Description

• 你被困在一个三维的空间中，现在要寻找最短路径逃生！
• 空间由立方体单位构成
• 你每次向上下前后左右移动一个单位需要一分钟
• 你不能对角线移动并且四周封闭
• 是否存在逃出生天的可能性？如果存在，需要多少时间？

Format

Input

多组测试数据。一组测试测试数据表示一个三维迷宫：

• 输入第一行是一个数表示空间的数量。
• 每个空间的描述的第一行为 $L$，$R$ 和 $C$（皆不超过 30）。
• $L$ 表示空间的高度。
• $R$ 和 $C$ 分别表示每层空间的行与列的大小。
• 随后 $L$ 层地牢，每层 $R$ 行，每行 $C$ 个字符。
• 每个字符表示空间的一个单元。# 表示不可通过单元，. 表示空白单元。你的起始位置在 S，出口为 E。
• 每层空间后都有一个空行。$L$，$R$ 和 $C$ 均为 $0$ 时输入结束。

Output

每个空间对应一行输出。

如果可以逃生，则输出如下：

Escaped in x minute(s).

$x$ 为最短脱离时间。

如果无法逃生，则输出如下：

Trapped!

Samples

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

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

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

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

0 0 0

Escaped in 11 minute(s).
Trapped!

Hint

对于题目给出数据的含义就是输入 $L$，$R$，$C$，分别代表迷宫有 l 层，每层长宽分别是 $C$，$R$。对于数据以可以这样移动:

 (1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->

 (1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,,5)

共 11 步就可以到达终点 对于数据二明显不能到达，则输出 Trapped!

这题用 BFS 解，每次去队首元素，如果是终点则输出结果移动的次数，否则，从该点开始分别向东南西北上下移动（如果可以走的话）并继续搜，如果到队列为空还没搜到解法，则说明无解。

Limitation

1s, 1024KiB for each test case.