Cho số nguyên dương ~n~. Tìm số nguyên không âm ~k~ nhỏ nhất sao cho tích các số ~1! * 2! * 3! ... * k!~ thì chia hết cho ~n~. Định nghĩa ~x!~ là tích của ~x~ số nguyên dương đầu tiên.

Input

Một dòng duy nhất gồm số ~n~ với ~1 \le n \le 10^{14}.~

Output

Một dòng duy nhất là đáp số của bài toán.

Sample input 1

3

Sample output 1

3

Sample input 2

4

Sample output 2

3

Sample input 3

6

Sample output 3

3

Giải thích

Dễ thấy ứng với ~n=3,4,6~ thì đáp số đều là ~k=3~, vì ~1! * 2! * 3! = 12~ trong khi với ~k=2~ thì ~1! 2! = 2~ đều chưa thỏa mãn được điều kiện.

Subtasks

• Có ~50\%~ test ứng với ~n \le 10^5.~

• Có ~50\%~ test ứng với ~10^5 < n \le 10^{14}.~