Iroha 同 Kaguya 最近迷上咗一種基於整數嘅數學遊戲。

最初，佢哋共有一個正整數 $n$。兩個人輪流進行操作；一輪定義為 Iroha 同 Kaguya 各完成一次操作。喺每一輪入面：

1. Iroha 先手：佢必須揀一個非負整數 $x$（$0\le x<n$），並將當前嘅 $n$ 替換為 $n+x$。

2. Kaguya 後手：佢必須揀一個能夠整除當前 $n$ 嘅質數 $p$（即係 $p\mid n$），並將當前嘅 $n$ 替換為 $\frac{n}{p}$。

上述操作不斷重複。如果喺任意一輪結束之後 $n=1$，遊戲即刻結束。

喺遊戲入面，Iroha 希望最大化遊戲進行嘅總輪數，而 Kaguya 希望最小化總輪數。假設兩個人都完全理性而且採用最優策略，請確定遊戲最終會持續嘅總輪數。

輸入格式

第一行包含一個整數 $n$（$1\le n\le10^{18}$），表示遊戲嘅初始數。

輸出格式

輸出一行，包含一個整數，表示雙方都採用最優策略嗰陣遊戲持續嘅總輪數。

樣例

樣例輸入 1

1

樣例輸出 1

0

樣例輸入 2

9

樣例輸出 2

4

樣例輸入 3

16

樣例輸出 3

5