Задача Lotto

Компания Megasoft организовала телевикторину. На табло появляется натуральное число. Участник должен дописать к нему справа несколько цифр (обязательно хотя бы одну) так,чтобы получилось простое число и прислать SMS с полученным числом в студию. Участник, приславший свое число первым, эту сумму и выигрывает. Владелец компании Megasoft Гилл Бейтс известен своей жадностью и не хочет платить лишние деньги. Поэтому он решил негласно изменить правила. Теперь выигрыш получит тот участник викторины, который первым пришлет наименьшее возможное  число. Помогите Г.Бейтсу определить сумму выигрыша согласно новым правилам.

Технические условия.
Программа читает с клавиатуры натуральное число, не большее 1000000. Программа выводит на экран минимальное число, которое можно получить по новим правилам викторины,то есть сумму, с которой Г.Бейтс вынужден распрощаться.
Примеры
Ввод
12
Вывод
127
Ввод
41
Вывод
419