You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

写作业

题目描述

老师需要把一个字输入 $n$ 遍，这个字老师已经输入到文档里了。然后他有事，把这个任务交给小容了。

小容想了想，有个功能叫复制粘贴啊。如果已经有 $x$ 个字，小容可以选择：

• 1.往文档最后加一个字。字数变成 $x+1$；
• 2.把文档复制粘贴一遍。字数变成 $2x$。

问小容至少需要多少次操作，才能得到恰好 $n$ 个字。

输入格式

仅一行，一个正整数 $n$。

输出格式

仅一行，一个正整数，表示最少操作次数。

样例 #1

样例输入 #1

16

样例输出 #1

4

样例 #2

样例输入 #2

5

样例输出 #2

3

提示

样例解释

样例数据1，$1\to 2\to 4\to8\to 16$，共 4 步。

样例数据2，$1\to 2\to 4\to 5$，共 3 步。

数据规模与约定

对于 $50\%$ 的数据，$n\leq 10^6$。 对于 $100\%$ 的数据，$n\leq 10^{12}$。