Cho số $n$ nguyên dương, bạn có thể thực hiện một trong hai thao tác sau bao nhiêu lần tùy ý:

• Nhân số nguyên tố $p$ bất kì cho $n$.
• Lấy $n$ chia cho số nguyên tố $p$ bất kì.

Cần thực hiện ít nhất bao nhiêu lần thao tác trên thì thu được một số có dạng $a^b$ với $a,b>1$ ?

Đầu vào

Một số nguyên $n$ duy nhất $(1<n\le {10}^{12})$.

Đầu ra

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Đầu vào:

6

Đầu ra:

2