Большая Манила сегодня состоит из пяти окружных дорог, расположенных в виде концентрических полуокружностей. Шестая дорога вскоре будет построена и соединит север и юг. Из центра (Манилы) выходит десять радиальных линий, соединяющих внутренние и внешние области Метрополии Манилы.
Рисунок 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", если невозможно добраться до места назначения.