The young mathematician Vasya continued his research in number theory. This time he studied the concept of greatest common divisor of two integers (). Recall that the of two integers and is the largest integer by which both and are divisible without a remainder. Vasya calls a natural number good with respect to the natural number , if \gcd(x, n) = x. For example, the good numbers with respect to are , , and . Vasya calculated the count of good numbers with respect to and received the number . But bad luck: he got so confused in his calculations that he could not remember the number for which he performed the computation. Help him find this value and determine the smallest number for which he could get such a response. It is known that the number for which Vasya carried out the calculations does not exceed 10^{18}.
The input file contains a unique number (1 \leq m \leq 1000).
In a single line output the smallest positive integer not exceeding 10^{18} that has exactly good numbers, or if no such numbers exist.
Example 1