The 2 x 2 x 2 Rubik's Cube

Sonny is probably the only computer-science Ph.D. student who cannot solve a Rubik's cube. One day he came across a neat little 2 x 2 x 2 Rubik's cube and thought, "Finally, a cube easy enough for me to solve!" He was wrong, and got thoroughly beaten. How embarrassing.

To make sure this never happens again, he decides to write a program that solves the cube. Then he had a brilliant idea: why not have the contestants do the work instead? So, given an initial configuration of a 2 x 2 x 2 Rubik's cube, your task is to figure out how quickly it can be solved.

The mini-cube has 6 faces, each with 4 painted tiles. The faces are labeled Front (F), Back (B), Up (U), Down (D), Left (L), and Right (R), as in the diagram below. Each tile is colored Red (R), Green (G), Blue (B), Yellow (Y), Orange (O), or White (W), and there are exactly 4 tiles of each color. The cube is solved when all four tiles on every face share the same color.

You may use any combination of three distinct moves: a turn about the X-axis, a turn about the Y-axis, or a turn about the Z-axis. Each turn rotates one half of the cube by exactly 90 degrees, in the direction shown below. The back-down-left corner stays fixed under every valid move (so each axis has exactly one turn direction).

Given a configuration, how few moves are needed to solve it?

You are given maps of an "unwrapped" cube showing the colors on each face, in the following format:

..UU....
..UU....
LLFFRRBB
LLFFRRBB
..DD....
..DD....

The letters above show where each face's colors appear on the map (matching the first diagram) -- this is only a legend, not valid input. The front face is oriented as in the diagram, with the other faces attached around it so the map wraps to cover the cube. On a real map the tile letters are any of R, G, B, Y, O, or W. Dot (.) characters pad the map to a 6 x 8 grid and carry no other meaning.

The input contains several configuration maps in this format, separated by blank lines. Every configuration is valid and solvable. The input ends with an "empty" configuration consisting solely of '.' characters; do not process that map.

For each cube, output on a single line the minimum number of moves needed to solve it. A move is a single 90-degree turn about the X, Y, or Z axis, always taken in the fixed direction shown above. If the cube is already solved, output 0.