상범 빌딩

당신은 상범 빌딩에 갇히고 말았다. 이곳을 탈출하는 가장 빠른 방법은 무엇일까?

상범 빌딩은 한 변의 길이가 $1$인 단위 정육면체들로 이루어져 있다. 각 정육면체는 금으로 꽉 차 있어 지나갈 수 없거나, 비어 있어 지나갈 수 있다. 당신은 현재 칸에서 인접한 $6$개의 칸(동, 서, 남, 북, 위, 아래) 중 하나로 $1$분에 한 칸씩 이동할 수 있다. 대각선으로는 이동할 수 없다. 빌딩의 바깥면은 모두 금으로 막혀 있으므로, 오직 출구를 통해서만 밖으로 나갈 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 탈출할 수 있다면 시간이 얼마나 걸릴까?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $L$, $R$, $C$가 주어진다. $L,(1 \le L \le 30)$은 빌딩의 층 수이고, $R,(1 \le R \le 30)$과 $C,(1 \le C \le 30)$은 한 층의 행과 열의 개수이다.

이어서 $C$개의 문자로 이루어진 행이 $R$개씩, 모두 $L$개 층에 대해 주어진다. 각 문자는 빌딩의 한 칸을 나타낸다.

• # : 금으로 막혀 지나갈 수 없는 칸
• . : 비어 있어 지나갈 수 있는 칸
• S : 당신의 시작 지점
• E : 탈출할 수 있는 출구

각 층 사이에는 빈 줄이 하나씩 있다. 시작 지점과 출구는 각각 항상 하나만 존재한다. 입력의 끝은 $L$, $R$, $C$가 모두 $0$인 줄로 표시되며, 이 줄은 처리하지 않는다.

각 빌딩에 대해 한 줄씩 답을 출력한다. 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 빌딩을 탈출하는 데 필요한 최단 시간(분)이다. 탈출이 불가능하다면 다음과 같이 출력한다.

Trapped!