Score : $400$ points

Problem Statement

You are given an integer $K$ greater than or equal to $2$. Find the minimum positive integer $N$ such that $N!$ is a multiple of $K$.

Here, $N!$ denotes the factorial of $N$. Under the Constraints of this problem, we can prove that such an $N$ always exists.

Constraints

• $2\leq K\leq 10^{12}$
• $K$ is an integer.

Input

The input is given from Standard Input in the following format:

$K$

Output

Print the minimum positive integer $N$ such that $N!$ is a multiple of $K$.

30

5

• $1!=1$
• $2!=2\times 1=2$
• $3!=3\times 2\times 1=6$
• $4!=4\times 3\times 2\times 1=24$
• $5!=5\times 4\times 3\times 2\times 1=120$

Therefore, $5$ is the minimum positive integer $N$ such that $N!$ is a multiple of $30$. Thus, $5$ should be printed.

123456789011

123456789011

280

7