题目描述

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

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

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

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

输入格式

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

$N$

输出格式

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

题目大意

给定一个不大于 $10^{18}$ 的一个正整数 $n$ ，求在所有满足 $a×2^b+c$ 的非负整数三元组 $(a,b,c)$ 中， $a+b+c$ 的最小值。

998244353

143

1000000007

49483

1

1

998984374864432412

2003450165

提示

制約

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

Sample Explanation 1

$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$ と出力すれば正解となります。

Sample Explanation 2

$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$ と出力すれば正解となります。

Sample Explanation 3

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