Tobo или не Tobo
Игра Тобо проводится на пластиковой доске, разделенной на сетку 3×3 с ячейками, пронумерованными от 1 до 9, как показано на рисунке (a). На сетке расположены четыре циферблата (обозначенные буквами "A" до "D" на рисунке). Каждый циферблат может вращаться на 90 градусов в любом направлении. Вращение циферблата приводит к повороту четырех ячеек, которые в данный момент находятся рядом с ним. Например, рисунок (b) демонстрирует Тобо после однократного вращения циферблата "A" по часовой стрелке. Рисунок (c) показывает Тобо на рисунке (b) после однократного вращения циферблата "D" против часовой стрелки.
Дети любят бросать вызов друг другу, играя в Тобо. Начиная с расположения, показанного на рисунке (a) (которое мы будем называть стандартным расположением), один ребенок случайным образом вращает циферблаты X раз, чтобы "перемешать" доску. Затем другой ребенок пытается вернуть доску в ее стандартное расположение, затратив не более X вращений. Чем меньше вращений потребуется для восстановления, тем лучше. Здесь вы видите бизнес-возможность. Вы хотите продать этим детям программу, которая будет советовать им минимальное количество шагов, необходимых для возвращения Тобо в его стандартное расположение.
Входные данные
Ваша программа будет тестироваться на одном или нескольких тестовых случаях. Каждый тестовый случай задается в отдельной строке. Каждая строка состоит из 10 десятичных цифр. Назовем первую цифру Y. Оставшиеся 9 цифр не равны нулю и описывают текущее расположение Тобо в порядке строк сверху вниз, слева направо. Первый пример соответствует рисунку (c).
Последняя строка входного файла — это последовательность из 10 нулей.
Выходные данные
Для каждого тестового случая выведите результат в следующем формате:
k. R
где k — номер тестового случая (начиная с 1), пробел, и R — минимальное количество вращений, необходимых для возвращения Тобо в его стандартное расположение. Если это невозможно сделать за Y вращений или меньше, то R = -1.