Problem F
Next Same-Factored

Time Limit: 6 Seconds

Just print out the next integer number which has the same prime factors as the given number and is less than 2,000,000.

Input

There will be several test cases (at most 100,000). Each case is a single positive integer n that is less than 1,000,000, on a separate line.

Output

For each test case, output a line containing a single integer which is the next integer number that have the same prime factors as n. In the case that there is no such number print one line stating "Not Exist!".

Sample Input                               Output for Sample Input

2

143

991

4

1573

982081