Prime Path
Міністри кабінету були досить засмучені повідомленням від начальника служби безпеки, в якому йшлося про те, що їм усім доведеться змінити чотиризначні номери кімнат на своїх офісах.
— Це питання безпеки змінювати такі речі час від часу, щоб тримати ворога в невіданні.
— Але подивіться, я вибрав свій номер 1033 з вагомих причин. Я ж Прем'єр-міністр, знаєте!
— Я знаю, тому ваш новий номер 8179 також є простим числом. Вам просто доведеться наклеїти чотири нові цифри на чотири старі на дверях вашого офісу.
— Ні, це не так просто. Припустимо, що я зміню першу цифру на 8, тоді номер буде 8033, що не є простим числом!
— Я розумію, будучи прем'єр-міністром, ви не можете терпіти, щоб на ваших дверях було непросте число навіть кілька секунд.
— Правильно! Тому я повинен придумати схему переходу від 1033 до 8179 шляхом простих чисел, де змінюється лише одна цифра з одного простого на наступне просте.
Тут втрутився міністр фінансів, який підслуховував.
— Ніяких зайвих витрат, будь ласка! Я випадково знаю, що ціна однієї цифри - один фунт.
— Гм, у такому разі мені потрібна комп'ютерна програма, щоб мінімізувати витрати. Ви не знаєте якихось дуже дешевих програмістів, чи не так?
— Насправді, знаю. Бачите, зараз проходить конкурс програмування... Допоможіть прем'єр-міністру знайти найдешевший шлях простих чисел між будь-якими двома заданими чотиризначними простими числами! Перша цифра, звісно, має бути ненульовою. Ось рішення у випадку вище.
1033 1733 3733 3739 3779 8779 8179
Вартість цього рішення становить 6 фунтів. Зверніть увагу, що цифра 1, яка була наклеєна на кроці 2, не може бути повторно використана на останньому кроці — потрібно придбати нову 1.
Вхідні дані
Один рядок з позитивним числом: кількість тестових випадків (не більше 100). Потім для кожного тестового випадку один рядок з двома числами, розділеними пробілом. Обидва числа є чотиризначними простими числами (без провідних нулів).
Вихідні дані
Один рядок для кожного випадку, або з числом, що вказує мінімальну вартість, або зі словом Неможливо.