Prime Path
Министры кабинета были весьма обеспокоены сообщением от начальника службы безопасности, в котором говорилось, что всем им придется изменить четырехзначные номера комнат в их офисах.
— Это вопрос безопасности, менять такие вещи время от времени, чтобы держать врага в неведении.
— Но посмотрите, я выбрал свой номер 1033 по веским причинам. Я ведь премьер-министр, знаете ли!
— Я знаю, поэтому ваш новый номер 8179 тоже простое число. Вам просто нужно будет наклеить четыре новых цифры поверх четырех старых на двери вашего офиса.
— Нет, это не так просто. Предположим, я изменю первую цифру на 8, тогда число будет 8033, которое не является простым!
— Понимаю, будучи премьер-министром, вы не можете терпеть, чтобы на вашей двери было не простое число даже на несколько секунд.
— Верно! Поэтому я должен придумать схему перехода от 1033 к 8179 по пути простых чисел, где изменяется только одна цифра от одного простого числа к следующему.
Теперь вмешался министр финансов, который подслушивал.
— Пожалуйста, никаких ненужных расходов! Я как раз знаю, что цена одной цифры составляет один фунт.
— Хм, в таком случае мне нужна компьютерная программа, чтобы минимизировать затраты. Вы не знаете каких-нибудь очень дешевых программистов?
— На самом деле, знаю. Видите ли, сейчас проходит конкурс программирования... Помогите премьер-министру найти самый дешевый путь между любыми двумя заданными четырехзначными простыми числами! Первая цифра, конечно, не должна быть нулевой. Вот решение в приведенном выше случае.
1033 1733 3733 3739 3779 8779 8179
Стоимость этого решения составляет 6 фунтов. Обратите внимание, что цифра 1, которая была наклеена во втором шаге, не может быть использована повторно в последнем шаге — нужно купить новую 1.
Входные данные
Одна строка с положительным числом: количество тестов (не более 100). Затем для каждого теста одна строка с двумя числами, разделенными пробелом. Оба числа — четырехзначные простые числа (без ведущих нулей).
Выходные данные
Одна строка для каждого случая, либо с числом, указывающим минимальную стоимость, либо содержащая слово Impossible.