10. Gandalf and Elven Numerology

Это ну очень неформальная задача с очень невнятным условием.

Числа, как известно, бывают счастливыми и несчастливыми. Причём критериев для этого много: и исторические традиции разных стран, и всевозможные арифметические действия...

Есть свои критерии и у эльфов. Как они определяют «удачливость» числа – неясно. По-видимому, это некая функция от натурального числа. Обозначим её U(N). Известно, что U(2021) = 420, и это самое удачное число XXI века. А вот, к примеру, 2020 был плохим, его удачливость равна 0, как и у 2022. А вот U(2023) = 6.

Формулу эльфы никому не раскрывают, но охотно оценивают удачливость различных чисел. Когда Гэндальф спросил эльфов, удачное ли число волосков у него в бороде (на момент вопроса их было 273817387), ему ответили, что сейчас удачливость его бороды нулевая, но вот если вырвать 5 волосков, она станет равной 54486542, но это не предел, можно и большего добиться.

Количество волос в бороде у Гэндальфа меняется в полночь, оно не меньше 1 и не больше миллиарда. И вот теперь Гэндальф каждое утро вырывает клок бороды таким образом, чтобы оставшиеся в ней волоски образовывали максимально удачливое число. Но чтобы знать, сколько волос выдрать, Гэндальфу приходится звонить эльфам, а мобильная связь в Средиземье дорогая…

Разработайте программу, которая по текущему количеству волос в бороде Гэндальфа определяет, сколько волосков надо вырвать для достижения максимальной удачливости. Если есть несколько вариантов – выбирайте тот, где волосков выдирается меньше.

Входные данные: одно натуральное число – количество волосков в бороде Гэндальфа.

Выходные данные: одно число – количество волосков, которые следует вырвать для достижения максимальной возможной удачливости.