题目描述

在AtCoder的问题中，你经常被要求：

求解模 $998244353$ 的答案。

在这里，我们有 $998244353 = 119 \\times 2^{23} + 1$。与此相关的，解决以下问题：

给定一个整数 $N$。
打印非负整数三元组 $(a, b, c)$ 的 $a + b + c$ 的最小可能值，满足 $N = a \\times 2^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