В прошлом семестре студенты матмеха Екатеринозаводского университета должны были сдавать экзамен по сетевым технологиям. N преподавателей, ведущих этот предмет, договорились между собой следующим образом: за семестр по этому предмету состоится N2 лабораторных работ, причём первый преподаватель проведёт лабораторные с номерами 1, N + 1, 2N + 1, …,
N2 − N + 1, второй — лабораторные
с номерами 2, N + 2, 2N + 2, …,
N2 − N + 2, и так далее. N-й преподаватель проведёт лабораторные с номерами N, 2N, 3N, …, N2. Также преподаватели вспомнили, что за последние
годы ленивые студенты стали пропускать много лабораторных, из-за чего потом плохо сдают экзамен. Поэтому они решили, что студент будет допущен к экзамену только если посетит хотя бы одну лабораторную каждого преподавателя.
N студентов, живущих в одной комнате общежития, не знали, сколько лабораторных состоится в течение семестра и сколько преподавателей ведёт их. У этих студентов было разное отношение к учёбе: первый студент в течение семестра ходил на все лабораторные, второй — только на лабораторные с номером, кратным двум, третий —
только на лабораторные с номером, кратным трём, и так далее… После завершения всех лабораторных оказалось, что к экзамену допущено лишь K из этих студентов.
Исходные данные
Целое число K (1 ≤ K ≤ 2·109).
Результат
Выведите минимально возможное N, удовлетворяющее условию задачи. Если ни для какого N к экзамену не может быть допущено ровно K студентов, выведите 0.
Примеры
исходные данные | результат |
---|
8
| 15 |
3
| 0 |
Автор задачи: Игорь Чевдарь
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2008