题目描述

给定一个正整数 $n$，最少需要多少次乘法运算才能从 $a$ 算出 $a^n$ 呢？

例如当 $n=5$ 的时候，最少需要 $3$ 次乘法：

当 $n=23$ 的时候，最少需要 $6$ 次乘法，具体步骤为

• 令 $x_0=a$；
• 计算 $x_1=x_0\cdot x_0=a^2$；
• 计算 $x_2=x_0\cdot x_1=a^3$；
• 计算 $x_3=x_1\cdot x_2=a^5$；
• 计算 $x_4=x_3\cdot x_3=a^{10}$；
• 计算 $x_5=x_4\cdot x_4=a^{20}$；
• 计算 $x_6=x_2\cdot x_5=a^{23}$。

输入格式

单个整数表示 $n$。

输出格式

单个整数表示最少的乘法运算次数。

5

3

9

4

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 1000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 10000$；