Допуск до екзамену
У минулому семестрі студенти матмеху Єкатеринозаводського університету повинні були здавати іспит з мережевих технологій. 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.