Lũy Thừa Chưa Dùng · canuc80k0816

Ban đầu có số nguyên dương $N$ . Một thao tác chọn một số $z$ có dạng $p^{e}$ , trong đó $p$ là số nguyên tố và $e$ là số nguyên dương, sao cho:

giá trị hiện tại của $N$ chia hết cho $z$ (tức $z$ là một ước của $N$ );
giá trị $z$ chưa từng được chọn ở thao tác trước.

Sau đó thay $N$ bằng $N / z$ . Hãy tìm số thao tác lớn nhất có thể thực hiện. Có thể dừng khi không còn lựa chọn hợp lệ; không bắt buộc giá trị cuối cùng bằng $1$ .

Input

Một dòng chứa số nguyên $N$ .

Output

In số thao tác lớn nhất.

Constraints

$1 \leq N \leq 1 0^{12}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 1 0^{6}$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Có thể lần lượt chọn $2, 4$ và $3$ : tích ba giá trị là $24$ chia $72$ , và ba lũy thừa đều khác nhau. Không thể thực hiện thao tác thứ tư.

Phân tích: Giả sử nguyên tố p có số mũ E trong N. Các lũy thừa của cùng p được chọn phải có số mũ dương khác nhau. Muốn có nhiều thao tác nhất, ta dùng các số mũ nhỏ nhất 1,2,...,k; chúng tiêu thụ tổng k(k+1)/2. Vì vậy đóng góp của p là k lớn nhất sao cho tổng này không vượt E.
Phân tích: Phân tích N thành thừa số nguyên tố, với mỗi số mũ ta trừ lần lượt 1,2,3,... và cộng số lần trừ được.
Chứng minh đúng: Bất kỳ k số mũ dương phân biệt nào cũng có tổng ít nhất 1+...+k, nên khi tổng đó vượt E thì k thao tác với p là bất khả thi. Khi tổng không vượt E, chọn đúng p^1,p^2,...,p^k là hợp lệ. Các nguyên tố khác nhau dùng phần số mũ độc lập, nên tổng các tối ưu riêng chính là tối ưu toàn cục.
Độ phức tạp: O(sqrt(N)) để phân tích, O(1) bộ nhớ phụ.