题目描述

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

输入格式

输入 $N$。

输出格式

输出一个整数，表示满足条件的 a+b+c 的最小值。

样例 #1

样例输入 #1

998244353

样例输出 #1

143

样例 #2

样例输入 #2

1000000007

样例输出 #2

49483

样例 #3

样例输入 #3

1

样例输出 #3

1

样例 #4

样例输入 #4

998984374864432412

样例输出 #4

2003450165

提示

样例说明 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 是正确的输出。

样例说明 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 是正确的输出。

样例说明 3

注意 $2^0\ =\ 1$ 。

数据范围

$1\le N \le 10^{18}$。