题目描述

给定一个整数 $N$。请找出满足以下条件的非负整数三元组 $(a, b, c)$ 中 $a + b + c$ 的最小值：
$N = a × 2^b + c$。

输入格式

输入$N$。

输出格式

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

样例

998244353

143

1000000007

49483

1

1

998984374864432412

2003450165

样例解释

【样例1说明】
我们有 $998244353 = 119 × 2^{23} + 1$，即三元组$(a, b, c) = (119, 23, 1)$ 满足 $N = a × 2^b + c$。
这个三元组的 $a + b + c$值为 143。
不存在$a + b + c ≤ 142$的满足条件的三元组，所以 143 是正确的输出。
【样例2说明】
我们有 $1000000007 = 30517 × 2^{15} + 18951$，即三元组 $(a, b, c) = (30517, 15, 18951)$ 满足$N = a × 2^b + c$。
这个三元组的 $a + b + c$值为 49483。
不存在 a + b + c ≤ 49482 的满足条件的三元组，所以 49483 是正确的输出。
【样例3说明】
注意 $2^0 = 1$。

数据范围

$1 ≤ N ≤ 10^{18}$，$N$ 是整数。

来源

• AtCoder ARC119A