Задача 57. Славный праздник ≡

Условие

...

Новый Год к нам мчится,

Скоро все случится,

Сбудется что снится,

Что опять нас обманут, ничего не дадут.

Ждать уже недолго,

Скоро будет елка.

Только мало толка,

Если Дед Мороза дети от беды не спасут.

...

Алексей Рыжов, "Новогодняя", 1999 г.

Видеоклип

Детский утренник проходил в полном соответствии со сценарием. Сказочные злодеи пустили по неверной дороге Снеговика, успешно похитили Снегурочку и лишили Деда Мороза мешка с подарками. Оставалось только разобраться с детьми (пятиклассниками Лицея программистов имени Фортрана), но, нашла коса на камень! Дети успешно закидали снежками Бабу Ягу, победили в музыкальном конкурсе Кота Баюна и вовремя завершили квест по поиску сундука Кащея Бессмертного! Настало время интеллектуальной схватки. Нечисть выставила Лешего, а ребята против него — отличника Лёшу.

Много хитрых вопросов задал Леший Лёше, но на все получил ответ. Понял, что честно не выиграть, и применил запрещённый приём — задал непосильную для пятиклассника задачку. Хорошо, что у ребят есть в запасе подсказка "Помощь зала", да вот найдётся ли среди зрителей сведущий программист?

Какое минимальное количество чисел из набора множителей от 1 до n нужно исключить, чтобы произведение оставшихся чисел не делилось на 2023?

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере дано n = 34.

34! = 295232799039604140847618609643520000000, действительно делится на 2023 нацело.

Если вычислить 33! = 8683317618811886495518194401280000000, то это число на 2023 уже не делится. Значит, достаточно вычеркнуть одно число.

Во втором примере дано n = 5.

5! = 120, не делится на 2023, ни одного числа вычеркивать не нужно.

Примеры тестов

34

1

5

0