Tobo or not Tobo#1330
The game of Tobo is played on a plastic board with a 3\times3 grid, where the cells are numbered from to as shown in figure (a). The grid has four dials (labeled "A" to "D" in the figure). Each dial can be rotated in degree increments in either direction. Rotating a dial causes the four adjacent cells to rotate with it. For example, figure (b) shows the Tobo after rotating dial "A" once clockwise. Figure (c) shows the Tobo in (b) after rotating dial "D" once counterclockwise.
Kids like to challenge each other using the Tobo board. Starting from the arrangement in figure (a) (the standard arrangement), one child randomly rotates the dials times to shuffle the board. Another child then tries to return the board to the standard arrangement, using at most rotations. Fewer rotations is better. Here is where you see a business opportunity: you want to sell these kids a program that advises them on the minimum number of steps required to restore the Tobo to its standard arrangement.
Your program will be tested on one or more test cases. Each test case is given on its own line. Each line consists of decimal digits. Let the first digit be . The remaining digits are non-zero and describe the current Tobo arrangement in row-major order (top to bottom, left to right). The first sample corresponds to figure (c).
The last line of the input file is a sequence of zeros.
For each test case, print the result in the following format:
k. R
where is the test case number (starting from ), a space, and is the minimum number of rotations needed to restore the Tobo to its standard arrangement. If this cannot be done in rotations or fewer, then R=-1.
Example 1