Cho một số nguyên $n$ ($2 \le n \le 100000000$). Hãy viết chương trình tìm số nguyên dương $m$ nhỏ nhất sao cho giai thừa của $m$ chia hết cho $n$. Ở đây, đối với một số nguyên dương $m$, giai thừa của $m$ là tích của tất cả các số nguyên từ $1$ đến $m$.

Dữ liệu vào

Dữ liệu vào được cho trong tệp factorial.in. Tệp này gồm một dòng duy nhất chứa số nguyên $n$.

Kết quả

Chương trình cần in kết quả ra đầu ra chuẩn. Hãy in ra một dòng duy nhất chỉ chứa số nguyên $m$.

Ví dụ

Dữ liệu vào 1

10

Kết quả 1

5

Dữ liệu vào 2

12

Kết quả 2

4