Cho số nguyên dương ~K~. Hãy tìm số nguyên dương ~N~ nhỏ nhất thỏa mãn ~N!~ chia hết cho ~K~.

Input

• Dòng duy nhất chứa số nguyên ~K~ ~(1 \le K \le 10^{12})~.

Output

• In ra số nguyên dương ~N~ nhỏ nhất thỏa mãn ~N!~ chia hết cho ~K~.

Examples

Sample Input 1

15

Sample Output 1

5

Sample Input 2

7

Sample Output 2

7

Scoring

• Subtask ~1~ ~-~ ~500~ điểm: ~K \le 20~
• Subtask ~2~ ~-~ ~500~ điểm: ~K=2^i~ với ~i~ thỏa mãn ~1 \le i \le 39~
• Subtask ~3~ ~-~ ~750~ điểm: Không có ràng buộc gì thêm