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