Tobo чи не tobo#1330
Гра Tobo проводиться на пластиковій дошці з сіткою 3\times3, де клітини пронумеровані від до , як показано на рисунку (a). На сітці розміщені чотири індикатори (позначені на рисунку літерами "A" до "D"). Кожен індикатор можна обертати на градусів у будь-який бік. Обертання індикатора викликає одночасне обертання чотирьох сусідніх з ним клітин. Наприклад, рисунок (b) показує стан Tobo після одного обертання індикатора "A" за годинниковою стрілкою. Рисунок (c) показує Tobo з (b) після одного обертання індикатора "D" проти годинникової стрілки.
Діти люблять змагатись між собою, використовуючи дошку Tobo. Починаючи зі стандартного розташування, показаного на рисунку (a), одна дитина випадково обертає індикатори разів, щоб перемішати дошку. Інша дитина намагається повернути дошку до стандартного вигляду, використовуючи не більше обертів. Чим менше обертів, тим краще. Ось тут ви бачите бізнес-можливість: ви хочете продавати цим дітям програму, яка підкаже мінімальну кількість ходів, необхідних для повернення Tobo до стандартного розташування.
Вашу програму буде протестовано на одному або кількох тестових випадках. Кожен тестовий випадок наведено в окремому рядку. Кожен рядок складається з десяткових цифр. Перша цифра — це . Решта — ненульові і описують поточне розташування Tobo у порядку рядків (згори вниз, зліва направо). Перший приклад відповідає рисунку (c).
Останній рядок у вхідному файлі — це послідовність із нулів.
Для кожного тестового випадку виведіть результат у такому форматі:
k. R
де — номер тестового випадку (починаючи з ), пробіл, а — мінімальна кількість обертів, необхідна для повернення Tobo до стандартного розташування. Якщо це неможливо зробити за обертів чи менше, то R=-1.
Приклад 1