Об`їзд у Великій Манілі
Велика Маніла сьогодні складається з п'яти окружних доріг, розміщених у вигляді концентричних півкілець. Шоста дорога незабаром буде збудована і з'єднає північ та південь. З центру (Маніли) виходить десять радіальних ліній, які з'єднують внутрішні та зовнішні області Метрополії Маніли.
Рисунок 1 Ідеальна мережа доріг Великої Маніли
У цій задачі необхідно знайти найкоротший шлях від точки A до точки B. Кожна точка задається перетином кільцевої та радіальної дороги (C#, R#) з центром у точці (C0, R0). Для рорахунків повідомимо, що відстань кожного відрізка по радіальній дорозі складає 1 одиницю, у той час як довжина однієї дуги дорівнює номеру відповідної дороги. Наприклад, відстань від (C1, R3) до (C2, R3) дорівнює одній одиниці, а відстань від (C3, R1) до (C3, R2) три одиниці. Найкоротша відстань від (C1, R2) до (C5, R1) дорівнює п'яти (див. жирну частину). Вважається, що рух по дорозі C6 дозволено.
Проте у зв'язку з новою системою кодування транспортним засобам заборонено користуватись радіальною дорогою, номер якої співпадає з останньою цифрою його номерного знака. Наприклад, машина під номером ABC-123 не може скористатись дорогою R3. Окружні дороги (крім C6) також мають обмеження. Машини, номери яких закінчуються на 1 та 2, не можуть рухатись по C1, 3 і 4 по C2, 5 і 6 по C3, 7 і 8 по C4, 9 і 0 по C5. Таким чином найкоротша відстань від (C1, R2) до (C5, R1) для машины під номером ABC-123 дорівнює п'яти одиницям, проте відстань дорівнює дев'яти одиницям для машини під номером CBA-321. Можуть бути також випадки, що машина не зможе доїхати до пункту призначення.
Вхідні дані
Вхідні дані складаються з декількох тестів. Для простоти у кожному тесті буде задаватись 5 однозначних чисел, відокремлених пропуском. Перші два числа вказують початкову точку, наступні два - кінцеву, а останнє число - останню цифру номерного знака. Між сусідніми тестами немає порожніх рядків, за останнім тестом йде рядок з одного нуля.
Вихідні дані
Для кожного тесту вивести його номер (починаючи з 1) і потрібну відстань. Вивести "not possible", якщо неможливо дістатись до пункту призначення.