An integer $n$ ($2 \le n \le 100000000$) is given. Write a program to find the smallest positive integer $m$ such that the factorial of $m$ is divisible by $n$. Here, for a positive integer $m$, the factorial of $m$ is the product of all integers from $1$ to $m$.

Input

The input is given in the file factorial.in. This file consists of a single line containing the integer $n$.

Output

The program should output the result to the standard output. Output a single line containing only the integer $m$.

Sample

Input 1

10

Output 1

5

Input 2

12

Output 2

4