Problem F - Sudokube

The Rubik's Cube, invented in 1974 by the Hungarian Ernő Rubik, is probably one of the best known puzzles in the world. Sudoku, a number puzzle invented in 1979 is another known puzzle that became famous in the present days after being a huge success in Japan.

It did not take a long time before someone came up with the idea of joining the main concepts of the two puzzles in one single challenge. Instead of colors, the cube has numbers, and the objective is to make each face of the cube have all different digits, as in each square of the normal Sudoku puzzle. They gave it the name of Sudokube.

For the purpose of this problem you will have your task simplified by only having to consider a 2x2x2 cube. It has digits in the range [1..4] and the objective is to go from a given configuration to a goal state, where each 2x2 cube face has all 4 different digits, without repetitions. Note that since every digit appears 6 times and that a single face can have the four numbers in many different forms, there will be more than one possible goal state, but every one of them is acceptable, as long as it respects the pre-defined condition of having every face with all the numbers.

As in the case of Rubik's cube, you can rotate 90 degrees a single face of the cube, which affects not only that face, but also the ones which are connected to it. We call a "move" to a single 90 degrees rotation of one cube face (note that you can rotate to both sides).

Can you solve this simplified Sudokube?

The Problem

Given a configuration of a 2x2x2 Sudokube, your task is to discover the minimum number of moves to reach a goal state, where each cube face has all the 4 digits from 1 to 4, and no digit is repeated on the same face.


The input will consist of 6 lines representing the configuration of a 2x2x2 Sudokube. Each line will contain 8 characters ('.' or a digit from 1 to 4), as explained on the following figure:

Description of input

In the figure, 'T' represents the top of the cube, 'F' means front, 'B' means back, 'L' means right, 'R' means right and 'b' means bottom. You can imagine this representation as a foldable model of the 3D cube. Just as an example, if you rotate the top face to the left, and considering the previous figure, the resulting Sudokube would become:

  .  . B1 B2  .  .  .  .
  .  . R1 R3  .  .  .  .
 LX B4 T2 T4 F2 RX b1 b2
 LX B3 T1 T3 F1 RX b3 b4
  .  . L2 L4  .  .  .  .
  .  . FX FX  .  .  .  .

See the sample input to better understand. You can be assured that the Sudokube will always be valid, that is, it will only contain digits from 1 to 4, and that it will be solvable, in the sense that it always exist a sequence of moves leading to a goal state. More than that, the Sudokube will be solvable in 5 moves at most.


The output should contain a single integer indicating the minimum number of moves (90 degrees rotations of a single face) needed to reach a goal state from the given configuration. If the input is already a goal state you should print a zero (0), meaning no moves are needed.

Sample Input


Sample Output


CPUP 2007
Universidade do Porto