The Pharaoh's Curse

Most contestants reached the Benelux Algorithm Programming Contest on time — all except a few unlucky souls who trusted a cheap car navigation system. A couple of wrong turns sent them completely off course, and they ended up scattered all over the world.

One of them, whom we will simply call S, wisely chose to travel by train. Sadly she still followed her navigation system's advice, and this morning she boarded a southbound train instead of heading north. After a few more bad directions she found herself locked inside a labyrinth deep within the pyramid of the Egyptian pharaoh Sok-O-Ban. The cavern she landed in was completely closed off, surrounded by solid rock on every side.

S drew a map of the tomb. In the floor she found several buttons. If every button were pressed at the same time, a hidden exit would open — but the instant any button is released, the door closes again.

She also found up to two sarcophagi filled with rocks. Each sarcophagus is a cube one meter on a side, exactly the size of a floor tile. Resting a sarcophagus on a button keeps that button pressed, which keeps the exit open. Using a portable sarcophagus transporter, S can push a sarcophagus exactly one meter straight ahead.

The tomb is a grid. In one step S moves one meter to an orthogonally adjacent tile (up, down, left, or right):

• She may move onto an empty tile or onto the exit tile.
• If the tile directly ahead of her holds a sarcophagus and the tile immediately beyond it is empty, she pushes that sarcophagus one meter forward and moves into its former tile. She cannot pull a sarcophagus, push two at once, or push one into a wall or into another sarcophagus.

The exit is open exactly while every button is held down by a sarcophagus. S escapes the moment she steps onto the exit tile with all buttons pressed. Determine the minimum number of steps she needs to escape, or report that escaping is impossible.

The first line contains a positive integer, the number of test cases. Each test case is given as follows:

• A line with two positive integers $h$ and $w$ ($h, w \le 50$): the height and width of the maze.
• $h$ lines of $w$ characters each — the map S drew — using these symbols:
  • # — a wall or otherwise impassable tile.
  • . — an empty tile. There are at most $100$ of them.
  • S — S's starting tile.
  • X — a sarcophagus. There are at most two of these.
  • B — a button.
  • E — the exit. There is exactly one exit, and it lies on the edge of the map.

The edge of the map contains only walls and the exit.

For each test case, print one line: the minimum number of steps S needs to escape the tomb, or impossible if she cannot escape. S always moves in one-meter steps along the grid lines, possibly pushing a sarcophagus.