Iroha と Kaguya は最近、整数に基づく数学ゲームに夢中になっています。
初めに、2 人は 1 つの正整数 $n$ を共有します。2 人のプレイヤーは交互に操作を行い、Iroha と Kaguya がそれぞれ 1 回ずつ操作を完了することを 1 ラウンドと定義します。各ラウンドでは：
Iroha が先に操作します。非負整数 $x$ ($0\le x<n$) を選び、現在の $n$ を $n+x$ に置き換えなければなりません。
Kaguya が次に操作します。現在の $n$ を割り切る素数 $p$（すなわち $p\mid n$）を選び、現在の $n$ を $\frac{n}{p}$ に置き換えなければなりません。
上記の操作を繰り返します。いずれかのラウンドの終了後に $n=1$ となった場合、ゲームは直ちに終了します。
ゲーム中、Iroha はラウンド数の合計を最大にしようとし、Kaguya はラウンド数の合計を最小にしようとします。両者が完全に合理的で、最適な戦略を採用すると仮定して、最終的にゲームが続くラウンド数の合計を求めてください。
入力
1 行目にはゲームの初期の数を表す整数 $n$ ($1\le n\le10^{18}$) が含まれます。
出力
両者が最適にプレイした場合にゲームが続くラウンド数の合計を表す整数を 1 つ、1 行に出力してください。
入出力例
入力 1
1
出力 1
0
入力 2
9
出力 2
4
入力 3
16
出力 3
5