Перестановки цифр

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Из цифр десятичной записи числа N строятся все возможные неповторяющиеся k-значные числа, где k строго меньше количества цифр в числе N.
2. Из полученных чисел выбираются только простые.
3. Полученное таким образом количество простых чисел является числом R.

Каждую цифру числа можно использовать ровно столько раз, сколько она встречается в этом числе. Например, для исходного числа 345 могут получены следующие числа: 3, 4, 5, 34, 35, 45, 43, 53, 54. Из них простые: 3, 5, 43, 53. Результатом является число R = 4.

Укажите максимальное число N, меньшее заданного натурального числа M, для которого R будет максимальным.

Входные данные

Входной файл INPUT.TXT содержит целое число M (2 ≤ M ≤ 10 000).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]