EZ-Sokoban

Sokoban is a well known Japanese puzzle game. The name means "warehouse keeper". Your goal is to push boxes onto their marked places inside a warehouse. To push a box, the cell right behind the box and the cell right in front of it must both be empty. You stand behind the box while pushing, and you can push only one box at a time. You cannot push a box off the board, and you cannot stand outside the board while pushing.

Look at the picture below.

Box 1 can be pushed in all four directions, because the four cells next to it are empty. Box 2 can be pushed only east or west; the cell south of it is not empty, so north and south are impossible. Box 3 cannot be pushed at all. Box 4 can be pushed only east or west, because a wall sits south of it.

Sokoban is PSPACE-complete, but this problem uses an easier variant. Here every box holds a strong magnet, so the boxes have to stay together almost all of the time. In a stable position all boxes are connected edge to edge: starting from any box you can reach every other box by stepping only between boxes that share an edge. If a push leaves the boxes disconnected, you are in dangerous mode, and the very next push has to make the boxes connected again.

Look at the picture below.

The position is stable, because all 4 boxes are connected edge to edge. Suppose you push the northmost box west.

Now you are in dangerous mode, because the northmost box touches no other box. The next push has to restore a stable position. Pushing that same box south does it.

The boxes are stable again.

An EZ-Sokoban puzzle is a board, a starting arrangement of the boxes, and a final arrangement where the boxes have to end up. Find a solution that uses the fewest box moves, or decide that the puzzle cannot be solved. The starting and the final arrangements are never in dangerous mode.

To keep things simple, you, the warehouse keeper, may jump at any moment to any empty cell of the board.

The first line holds the number of test cases, $T$.

Each test case starts with a line holding $R$ and $C$, the number of rows and columns of the board, separated by one space. The next $R$ lines hold $C$ characters each and describe the board:

• . is an empty cell
• # is a wall
• x is a goal, a cell where a box has to stand at the end
• o is a box
• w is a box that already stands on a goal

The number of boxes equals the number of goals.

Limits:

• $1 \le T \le 50$
• $1 \le R, C \le 12$
• the number of boxes is at least $1$ and at most $5$

For each test case print one line

Case #X: K

where $X$ is the test case number starting from 1, and $K$ is the smallest number of box moves that solves the puzzle. Print -1 if the puzzle cannot be solved.