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

你每做一次乘法，可以用已经算出来的任意两个幂相乘（两个可以相同）。例如当 n=5 时，最少需要 3 次乘法：

a^5 = (a^2)^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。

输出一个整数，表示最少需要的乘法次数。

样例解释

• n=5：a \to a^2 \to a^4 \to a^5，3 次；少于 3 次最多只能算出 a^4，所以答案是 3。

• n=9：a \to a^2 \to a^4 \to a^8 \to a^9，4 次。

数据范围

• 对于 30\% 的数据，1 \le n \le 20；

• 对于 60\% 的数据，1 \le n \le 1000；

• 对于 100\% 的数据，1 \le n \le 10000。

本题共 10 个测试点，每个 10 分。