Portal

You are inside an R by C grid. A cake sits somewhere else in the grid, and you want to reach the cell holding it in as few moves as possible. One move takes you one empty cell north, south, east or west.

You carry a portal gun that fires a yellow portal and a blue portal. Firing the gun north, south, east or west sends out a ball of energy, and a portal appears on the first wall the ball hits. Firing the gun does not count as a move. If you fire at the cake, the ball passes straight through it.

Once both a yellow portal and a blue portal exist, you can move into the yellow portal and come out of the blue one, and you can also travel the other way. Portals work only after both colors are placed.

Consider this grid.

Gray cells are walls, white cells are empty, and the red circle is your position.

Fire a blue portal east. The portal appears on the first wall the ball hits.

Next, fire a yellow portal south.

Move one step south.

Move one more step south and you enter the yellow portal and come out of the blue one.

Exactly one yellow portal and one blue portal exist at any time. If you fire a new blue portal west, for example, the earlier blue portal disappears.

A portal disappears only when the same color is fired again.

A portal is created on one side of a wall. If a wall has a portal on its east side, you must move into that wall from the east to pass through the portal. Entering from any other side runs you into the wall.

Two portals cannot sit on the same side of a wall. If you fire a portal at a wall side that already holds one, the second portal fails to form.

Given the maze, your starting position and the cake's position, find the minimum number of moves needed to reach the cell holding the cake. Firing the portal gun does not count as a move.

The first line contains the number of test cases, N. N test cases follow.

The first line of each test case contains two integers R and C separated by a space. R lines follow, each with C characters describing the map.

• .: an empty cell
• #: a wall
• O: your starting position
• X: the cake's position

Each test case contains exactly one O and exactly one X.

Every cell outside the grid is a wall, and you may create portals on those walls too.

Limits:

• $1 \le N \le 50$
• $1 \le R \le 15$
• $1 \le C \le 15$

For each test case, print one line in the form Case #X: Y, where X is the test case number and Y is the minimum number of moves needed to reach the cake. If the cake cannot be reached, print THE CAKE IS A LIE in place of Y.

The first test case of the first example is solved in four moves by the sequence below. Firing the portal gun does not count as a move.

1. Move one step east.
2. Fire a blue portal north.
3. Fire a yellow portal south.
4. Move one step north, entering the blue portal.
5. Fire a blue portal east.
6. Move one step south, entering the yellow portal.
7. Move one step west.
8. Eat the cake.