Cho số nguyên \(n\). Hãy tìm số nguyên dương nhỏ nhất \(m\) sao cho \(m!\) chia hết cho \(n\). Giai thừa \(m!\) là tích của tất cả các số nguyên từ \(1\) đến \(m\).

Giới hạn thời gian là \(0{,}5\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa số nguyên \(n\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chỉ chứa số nguyên \(m\) nhỏ nhất thỏa mãn yêu cầu.

Ràng buộc

• \(2 \le n \le 100\,000\,000\).

Phân nhóm

Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.

1. Bộ dữ liệu 1: \(20\) điểm.
2. Bộ dữ liệu 2: \(20\) điểm.
3. Bộ dữ liệu 3: \(20\) điểm.
4. Bộ dữ liệu 4: \(20\) điểm.
5. Bộ dữ liệu 5: \(20\) điểm.

Ví dụ

10

5

12

4