В прошлом семестре студенты матмеха Екатеринозаводского университета должны были сдавать экзамен по сетевым технологиям. N преподавателей, ведущих этот предмет, договорились между собой следующим образом: за семестр по этому предмету состоится N² лабораторных работ, причём первый преподаватель проведёт лабораторные с номерами 1, N + 1, 2N + 1, …, N² − N + 1, второй — лабораторные с номерами 2, N + 2, 2N + 2, …, N² − N + 2, и так далее. N-й преподаватель проведёт лабораторные с номерами N, 2N, 3N, …, N². Также преподаватели вспомнили, что за последние годы ленивые студенты стали пропускать много лабораторных, из-за чего потом плохо сдают экзамен. Поэтому они решили, что студент будет допущен к экзамену только если посетит хотя бы одну лабораторную каждого преподавателя.

N студентов, живущих в одной комнате общежития, не знали, сколько лабораторных состоится в течение семестра и сколько преподавателей ведёт их. У этих студентов было разное отношение к учёбе: первый студент в течение семестра ходил на все лабораторные, второй — только на лабораторные с номером, кратным двум, третий — только на лабораторные с номером, кратным трём, и так далее… После завершения всех лабораторных оказалось, что к экзамену допущено лишь K из этих студентов.

Целое число K (1 ≤ K ≤ 2·10⁹).

Выведите минимально возможное N, удовлетворяющее условию задачи. Если ни для какого N к экзамену не может быть допущено ровно K студентов, выведите 0.