ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Summer 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Admission to Exam

Time limit: 2.0 second
Memory limit: 64 MB
At the end of the previous semester the students of the Department of Mathematics and Mechanics of the Yekaterinozavodsk State University had to take an exam in network technologies. N professors discussed the curriculum and decided that there would be exactly N2 labs, the first professor would hold labs with numbers 1, N + 1, 2N + 1, …, N2N + 1, the second one — labs with numbers 2, N + 2, 2N + 2, …, N2N + 2, etc. N-th professor would hold labs with numbers N, 2N, 3N, …, N2. The professors remembered that during the last years lazy students didn't attend labs and as a result got bad marks at the exam. So they decided that a student would be admitted to the exam only if he would attend at least one lab of each professor.
N roommates didn't know the number of labs and professors in this semester. These students had different diligence: the first student attended all labs, the second one — only labs which numbers were a multiple of two, the third one — only labs which numbers were a multiple of three, etc… At the end of the semester it turned out that only K of these students were admitted to the exam. Find the minimal N which makes that possible.

Input

An integer K (1 ≤ K ≤ 2·109).

Output

Output the minimal possible N which satisfies the problem statement. If there is no N for which exactly K students would be admitted to the exam, output 0.

Samples

inputoutput
8
15
3
0
Problem Author: Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008
To submit the solution for this problem go to the Problem set: 1673. Admission to Exam