ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1673. Допуск к экзамену

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В прошлом семестре студенты матмеха Екатеринозаводского университета должны были сдавать экзамен по сетевым технологиям. N преподавателей, ведущих этот предмет, договорились между собой следующим образом: за семестр по этому предмету состоится N2 лабораторных работ, причём первый преподаватель проведёт лабораторные с номерами 1, N + 1, 2N + 1, …, N2N + 1, второй — лабораторные с номерами 2, N + 2, 2N + 2, …, N2N + 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