問題文

$2$ 以上の整数 $N$ が与えられます。変数 $m$ があり、最初は $m=N$ です。

あなたはこの変数に対して、$1$ 回の操作で次のいずれかを行うことができます。

1. $m/2^k$ が整数となるような負でない整数 $k$ を選び、$m$ を $m/2^k$ に置き換える
2. 正の整数 $k$ を選び、$m$ を $mk+1$ に置き換える

あなたの目標は、できるだけ少ない操作回数で $m=N$ の状態から $m=1$ にすることです。目標を達成するために必要な操作回数の最小値を答えてください。

制約

• $2 \le N \le 10^9$

入力

$N$

出力

$m=N$ から $m=1$ にするために必要な操作回数の最小値を答えてください。

なお、この制約下で目標は必ず達成でき、答えは $2^{31}-1$ 以下であることが保証されます。

サンプル

4

1

3

2

6

3