Project Euler #70: Totient permutation

_{This problem is a programming version of Problem 70 from projecteuler.net}

Euler's Totient function, [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to which are relatively prime to . For example, as and are all less than nine and relatively prime to nine, .

The number 1 is considered to be relatively prime to every positive number, so . Interestingly, , and it can be seen that is a permutation of .

Find the value of , , for which is a permutation of and the ratio produces a minimum.

Input Format

Input contains an integer

Constraints

Output Format

Print the answer corresponding to the test case.

Sample Input

Sample Output