渴望力量的奶牛(Power Hungry Cows)

题目描述

FJ 的奶牛希望能够非常快速地计算整数的 $P$ 次幂（$1 \le P \le 20000$），但需要你的帮助。由于它们要计算非常大的数的幂，在计算过程中只能保留两个工作变量来存储中间结果。

第一个工作变量初始化为底数 $x$（即待求幂的数），另一个工作变量初始化为 $1$。在每一步操作中，奶牛可以将任意一对工作变量（也可以是同一个工作变量自身）相乘或相除，并将运算结果存入任意一个工作变量中，但所有中间结果必须始终为 $x$ 的非负整数次幂（整除无余项）。

例如，如果它们想计算 $x^{31}$，一种可行的方法如下图所示：

因此，$x^{31}$ 可以通过 $6$ 次运算求得。给定目标指数 $P$，请求出计算出 $x^P$ 所需的最少运算次数。

输入格式

输入仅一行一个正整数 $P$。

输出格式

输出一行一个整数，表示计算出 $x^P$ 所需的最少运算次数。

样例输入 #1

31

样例输出 #1

6

数据范围

对于 $100\%$ 的数据，$1 \le P \le 20000$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：2000。

测试点分布

出处：原题链接