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