本题没有可用的提交语言。

题目描述

从 ( x ) 出发，通过反复相乘可以计算出 ( x^{31} )， 但需要 30 次乘法。若允许使用平方操作，可显著缩短计算步骤。例如，使用 8 次乘法即可完成。若进一步允许除法，计算步骤还能更少——如通过 5 次乘法和 1 次除法（共 6 次操作）算出 ( x^{31} )。
你的任务是：对于给定的正整数 ( n )，计算从 ( x ) 出发，仅通过乘法和除法得到 ( x^n ) 所需的最少操作次数。 计算过程中出现的所有指数必须为正整数（即不能出现 ( x^{-3} ) 这样的指数）。

输入格式

• 输入包含多行，每行一个正整数 ( n )（( 1 \leq n \leq 1000 )），以 0 结束输入。

输出格式

• 对每个输入的 ( n )，输出一行整数，表示计算 ( x^n ) 所需的最少操作次数（乘法和除法的总次数）。

输入输出样例

题目来源

Japan 2006