Iroha và Kaguya gần đây rất say mê một trò chơi toán học dựa trên các số nguyên.

Ban đầu, họ có chung một số nguyên dương $n$. Hai người chơi lần lượt thực hiện các thao tác; một vòng chơi được định nghĩa là cả Iroha và Kaguya mỗi người hoàn thành một thao tác. Trong mỗi vòng:

1. Iroha đi trước: Cô ấy phải chọn một số nguyên không âm $x$ ($0\le x<n$) và thay thế số $n$ hiện tại bằng $n+x$.

2. Kaguya đi sau: Cô ấy phải chọn một số nguyên tố $p$ là ước của $n$ hiện tại (tức là $p\mid n$) và thay thế số $n$ hiện tại bằng $\frac{n}{p}$.

Các thao tác trên được lặp lại liên tục. Nếu $n=1$ sau khi kết thúc bất kỳ vòng nào, trò chơi sẽ kết thúc ngay lập tức.

Trong trò chơi, Iroha muốn tối đa hóa tổng số vòng chơi, trong khi Kaguya muốn tối thiểu hóa tổng số vòng chơi. Giả sử cả hai người chơi đều hoàn toàn lý trí và áp dụng chiến thuật tối ưu, hãy xác định tổng số vòng mà trò chơi cuối cùng sẽ kéo dài.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1\le n\le10^{18}$), biểu thị con số ban đầu của trò chơi.

Kết quả

In ra một dòng duy nhất chứa một số nguyên, biểu thị tổng số vòng mà trò chơi sẽ kéo dài khi cả hai người chơi đều chơi tối ưu.

Ví dụ

Dữ liệu vào 1

1

Kết quả 1

0

Dữ liệu vào 2

9

Kết quả 2

4

Dữ liệu vào 3

16

Kết quả 3

5