問題文

AtCoder ではたびたび、次のような形式の問題が出題されています。

答えを $998244353$ で割った余りを求めよ。

ところで、実は $998244353 = 119 \\times 2^{23} + 1$ という性質があります。それに関連して、次の問いに答えてください。

整数 $N$ が与えられる。
$N = a \\times 2^b + c$ を満たす非負整数の組 $(a, b, c)$ のうち、$a + b + c$ が最小となるものにおける $a + b + c$ の値を出力せよ。

制約

• $1 \\leq N \\leq 10^{18}$
• $N$ は整数

入力

入力は以下の形式で標準入力から与えられます。

$N$

出力

答えを出力してください。

入力例 1

998244353

出力例 1

143

$998244353 = 119 \\times 2^{23} + 1$ であるため、$(a, b, c) = (119, 23, 1)$ のとき等式 $N = a \\times 2^{b} + c$ が成り立ちます。
そのときの $a+b+c$ の値は $143$ です。
$a+b+c \\leq 142$ となるような組は存在しないため、$143$ と出力すれば正解となります。

入力例 2

1000000007

出力例 2

49483

$1000000007 = 30517 \\times 2^{15} + 18951$ であるため、$(a, b, c) = (30517, 15, 18951)$ のとき等式 $N = a \\times 2^{b} + c$ が成り立ちます。
そのときの $a+b+c$ の値は $49483$ です。
$a+b+c \\leq 49482$ となるような組は存在しないため、$49483$ と出力すれば正解となります。

入力例 3

1

出力例 3

1

$2^0 = 1$ であることに注意してください。

入力例 4

998984374864432412

出力例 4

2003450165