Đa thức ~P(x)~ hệ số nguyên, khác ~0,~ được gọi là liên kết với số nguyên dương ~m~ nếu như với mọi số ~a~ nguyên tùy ý thì đều có ~P(a)~ chia hết cho ~m~. Hãy xác định bậc nhỏ nhất của một đa thức nguyên nào đó có thể liên kết với ~m~.

Input

Một dòng duy nhất là số nguyên dương ~m~ với ~1 \le m \le 10^{14}.~

Output

Đáp số của bài toán.

Sample input 1

2

Sample output 1

2

Sample input 2

6

Sample output 2

3

Giải thích: trong VD1, ta cần tìm đa thức ~P(x)~ mà ~P(x)~ chia hết cho ~2~ với mọi ~x~ nguyên, dễ thấy bậc 1 không thỏa mãn, bậc hai thì có thể chọn ~P(x) = x(x-1)~ luôn chẵn với mọi ~x~ nguyên; trong VD2, ta chọn đa thức ~P(x) = x(x-1)(x-2)~ luôn chia hết cho ~2~ và ~3~ nên sẽ chia hết cho ~6.~