Допуск к экзамену
В прошлом семестре студенты матмеха Екатеринозаводского университета должны были сдавать экзамен по сетевым технологиям. N преподавателей, ведущих этот предмет, договорились между собой следующим образом: за семестр по этому предмету состоится N^2 лабораторных работ, причём первый преподаватель проведёт лабораторные с номерами 1, N+1, 2N+1, …, N^2−N+1, второй — лабораторные с номерами 2, N+2, 2N+2, …,N^2−N+2, и так далее. N-й преподаватель проведёт лабораторные с номерами N, 2N, 3N, …, N^2. Также преподаватели вспомнили, что за последние годы ленивые студенты стали пропускать много лабораторных, из-за чего потом плохо сдают экзамен. Поэтому они решили, что студент будет допущен к экзамену только если посетит хотя бы одну лабораторную каждого преподавателя.
N студентов, живущих в одной комнате общежития, не знали, сколько лабораторных состоится в течение семестра и сколько преподавателей ведёт их. У этих студентов было разное отношение к учёбе: первый студент в течение семестра ходил на все лабораторные, второй — только на лабораторные с номером, кратным двум, третий — только на лабораторные с номером, кратным трём, и так далее… После завершения всех лабораторных оказалось, что к экзамену допущено лишь K из этих студентов.
Входные данные
Целое число K (1 ≤ K ≤ 2·10^9).
Выходные данные
Выведите минимально возможное N, удовлетворяющее условию задачи. Если ни для какого N к экзамену не может быть допущено ровно K студентов, выведите 0.