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