题目描述

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$

输出格式

请输出答案。

样例 1

输入

998244353

输出

143

样例 2

输入

1000000007

输出

49483

样例 3

输入

1

输出

1

样例 4

输入

998984374864432412

输出

2003450165

说明/提示

限制条件

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

样例解释 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$。

由 ChatGPT 4.1 翻译