Tobo or not Tobo

Tobo is played on a plastic board built as a 3×3 grid whose cells are numbered 1 to 9, as shown in figure (a). The board has four dials, labelled A to D. Each dial can be turned 90° in either direction, and turning a dial rotates the four cells that currently surround it. For example, figure (b) shows the board after turning dial A one step clockwise, and figure (c) shows the board from figure (b) after turning dial D one step counter-clockwise.

The four dials sit at the interior corners of the grid: dial A is surrounded by cells 1, 2, 4, 5; dial B by cells 2, 3, 5, 6; dial C by cells 4, 5, 7, 8; and dial D by cells 5, 6, 8, 9. A single 90° turn cyclically shifts those four cells by one position in the chosen direction.

Kids love to challenge one another with the Tobo. Starting from the arrangement in figure (a) — the standard arrangement — one child turns the dials at random X times to shuffle the board. Another child then tries to bring it back to the standard arrangement using no more than X turns; the fewer turns, the better. Report the minimum number of turns needed to restore a given board to the standard arrangement.

The input contains one or more test cases, each on its own line. Every line is made of exactly 10 decimal digits. Call the first digit Y; it is the number of shuffle turns that were applied, and therefore the maximum number of turns you may use to restore the board. The remaining 9 digits are all non-zero and give the current arrangement in row-major order (top to bottom, left to right).

The input ends with a line of ten zeros, which must not be processed.

For each test case, print one line in the format:

k. R

where k is the test case number (starting at 1), the period is immediately followed by a single space, and R is the minimum number of turns needed to restore the board to the standard arrangement. If the board cannot be restored using at most Y turns, print R as -1 instead.