Шлях простих чисел

Міністри кабінету були досить засмучені повідомленням від начальника служби безпеки, в якому йшлося про те, що їм усім доведеться змінити чотиризначні номери кімнат на своїх офісах.

— Це питання безпеки, щоб збити ворога з пантелику.

— Але подивіться, я вибрав свій номер 1033 з вагомих причин. Я ж Прем'єр-міністр, знаєте!

— Я знаю, тому ваш новий номер 8179 також є простим числом. Вам просто доведеться наклеїти чотири нові цифри на чотири старі на дверях вашого офісу.

— Ні, це не так просто. Припустимо, що я зміню першу цифру на $8$, тоді номер буде 8033, що не є простим числом!

— Я розумію, будучи прем'єр-міністром, ви не можете терпіти, щоб на ваших дверях було непросте число навіть кілька секунд.

— Правильно! Тому я повинен придумати схему переходу від 1033 до 8179 шляхом простих чисел, де змінюється лише одна цифра з одного простого на наступне просте.

Тут втрутився міністр фінансів, який підслуховував.

— Ніяких зайвих витрат, будь ласка! Я випадково знаю, що ціна однієї цифри - один фунт.

— Гм, у такому разі мені потрібна комп'ютерна програма, щоб мінімізувати витрати. Ви не знаєте якихось дуже дешевих програмістів, чи не так?

— Насправді, знаю. Бачите, зараз проходить конкурс програмування... Допоможіть прем'єр-міністру знайти найдешевший шлях простих чисел між будь-якими двома заданими чотиризначними простими числами! Перша цифра, звісно, має бути ненульовою. Ось рішення у випадку вище.

1033 1733 3733 3739 3779 8779 8179

Вартість цього рішення становить $6$ фунтів. Зверніть увагу, що цифра $1$, яка була наклеєна на кроці $2$, не може бути повторно використана на останньому кроці — потрібно придбати нову $1$.