题目描述

机器猫要在电脑前打字。一共需要打 $n$ 个字，但现在文档里只有一个字。

机器猫有两种操作可以做。假设现在已经有 $x$ 个字，机器猫可以选择：

• 往文档最后加一个字。字数变成 $x+1$。
• 把文档复制粘贴一遍。字数变成 $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 步。

数据规模与约定

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

---

本题原题在洛谷：https://www.luogu.com.cn/problem/B3636