파라오의 저주

대부분의 참가자는 Benelux Algorithm Programming Contest 장소에 제시간에 도착했다. 하지만 값싼 차량 내비게이션을 믿었던 몇몇 불운한 이들은 길을 몇 번 잘못 들어 완전히 경로를 벗어났고, 결국 세계 곳곳으로 흩어지고 말았다.

그중 편의상 S라고 부를 참가자는 현명하게도 기차로 이동하기로 했다. 그러나 내비게이션의 안내를 그대로 따르다가 북쪽으로 가야 할 것을 남쪽으로 가는 기차에 올랐고, 몇 번 더 잘못된 안내를 거친 끝에 이집트 파라오 Sok-O-Ban의 피라미드 깊은 곳 미로에 갇히고 말았다. S가 떨어진 방은 사방이 단단한 바위로 완전히 막혀 있었다.

S는 무덤의 지도를 그렸다. 바닥에는 여러 개의 버튼이 박혀 있었다. 모든 버튼을 동시에 누르면 숨겨진 출구가 열리지만, 버튼 중 하나라도 떼는 순간 문은 다시 닫힌다.

방에는 돌로 가득 찬 석관도 최대 두 개 있었다. 각 석관은 한 변이 1미터인 정육면체로, 바닥 타일과 크기가 정확히 같다. 석관을 버튼 위에 올려 두면 그 버튼이 계속 눌린 상태가 되어 출구가 열린 채로 유지된다. S는 휴대용 석관 운반기를 이용해 석관을 정확히 1미터 앞으로 밀 수 있다.

무덤은 격자이다. 한 걸음에 S는 상하좌우로 인접한 한 칸(1미터)으로 이동한다.

• 빈 칸이나 출구 칸으로는 그냥 이동할 수 있다.
• 바로 앞 칸에 석관이 있고 그 석관 바로 너머 칸이 비어 있으면, 그 석관을 1미터 앞으로 밀고 석관이 있던 칸으로 들어간다. 석관을 당길 수는 없으며, 한 번에 두 개를 밀거나 벽 또는 다른 석관 쪽으로 밀 수도 없다.

출구는 모든 버튼이 석관에 의해 눌려 있는 동안에만 열린다. 모든 버튼이 눌린 상태에서 S가 출구 칸에 들어서는 순간 탈출에 성공한다. S가 탈출하는 데 필요한 최소 걸음 수를 구하라. 탈출이 불가능하면 그 사실을 알려라.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 양의 정수가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 미로의 높이와 너비를 나타내는 두 양의 정수 $h$, $w$ ($h, w \le 50$)가 적힌 한 줄.
• S가 그린 지도인, $w$개의 문자로 이루어진 $h$개의 줄. 다음 기호를 사용한다.
  • # — 벽 또는 지나갈 수 없는 칸.
  • . — 빈 칸. 빈 칸은 최대 $100$개이다.
  • S — S의 시작 칸.
  • X — 석관. 최대 두 개이다.
  • B — 버튼.
  • E — 출구. 출구는 정확히 하나이며, 지도의 가장자리에 있다.

지도의 가장자리에는 벽과 출구만 있다.

각 테스트 케이스마다 한 줄에, S가 무덤을 탈출하는 데 필요한 최소 걸음 수를 출력한다. 탈출할 수 없으면 impossible을 출력한다. S는 항상 격자 선을 따라 1미터씩 이동하며, 이동하면서 석관을 밀 수도 있다.