Sliding Block Puzzle

In sliding block puzzles, we repeatedly slide pieces (blocks) into open spaces within a frame to reach a goal arrangement of the pieces.

A puzzle creator has designed a new puzzle by combining the ideas of sliding block puzzles and mazes. The puzzle is played in a rectangular frame divided into unit squares. Some squares are pre-occupied by obstacles. Inside the frame there are several pieces: exactly one $2 \times 2$ king piece and some number of $1 \times 1$ pawn pieces. Exactly two $1 \times 1$ squares are left open. If a pawn piece is adjacent to an open square, we can slide that piece into it. If an entire edge of the king piece is adjacent to two open squares, we can slide the king piece one cell in that direction. Obstacles cannot be moved. Starting from a given initial placement, the goal is to move the king piece to the upper-left corner of the frame.

Your task is to write a program that computes the minimum number of moves needed to solve the puzzle from a given placement of pieces. Here, one move means sliding either the king piece or a single pawn piece to an adjacent position.

The input is a sequence of datasets. The first line of a dataset contains two integers $H$ and $W$ separated by a space, where $H$ and $W$ are the height and the width of the frame. Each of the following $H$ lines contains $W$ characters describing the initial placement of the pieces. In those lines, X, o, *, and . denote a part of the king piece, a pawn piece, an obstacle, and an open square, respectively. No other characters appear. You may assume that $3 \le H \le 50$ and $3 \le W \le 50$.

A line containing two zeros separated by a space marks the end of the input.

For each dataset, output on its own line the minimum number of moves required to move the king piece to the upper-left corner. If it is impossible, output -1.