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, …, N^2−N+1, the second one — labs with numbers 2, N+2, 2N+2, …, N^2−N+2, etc. N-th professor would hold labs with numbers N, 2N, 3N, …, N^2. 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.
An integer K (1 ≤ K ≤ 2·10^9).
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.