题目描述

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

例如当$n=5$ 的时候，最少需要 $3$次乘法： $a^5=\left(a^2\right)^2\cdot a$

当$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。

输出格式

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

数据规模

对于 100%的数据:$1\le n\le {10}^4$

---

正解只有85%的正确度,所以只能求近似解吗？