Description

FJ 的奶牛们希望能够快速计算整数幂 $P$（$1 \leq P \leq 20000$），但她们需要你的帮助。因为她们将要计算非常大的数的幂，所以她们只能保留两个工作变量来存储中间结果。

这两个工作变量中的第一个被初始化为正在计算幂的数字（表示为 $x$）；另一个被初始化为 $1$。奶牛们可以对任意一对工作变量进行乘法和除法运算，并将结果存储在任意一个工作变量中，但所有结果都存储为整数。

例如，如果她们想要计算 $x^{31}$，一种进行计算的方法是：

因此，$x^{31}$ 可以在六次操作中计算出来。给定要计算的幂和工作变量的数量，找出计算该幂所需的最少操作数。

Input Format

一行，一个整数：$P$。

Output Format

一行，一个整数，表示计算幂所需的最小操作数。

翻译来自于：ChatGPT

31

6