3685. 幂次计算

【题目描述】

刚刚学过快速幂的小明可高兴了，想去$oj$上刷题练练手，【幂次计算】，一看就是个简单题目，可是做着做着发现自己怎么都做不对，作为小明的学长，请你帮助他一下吧。

你的任务是编写一个程序，通过对给定的正整数 $n$ 进行从 $x$ 开始的乘法和除法运算，找到计算出 $x$ 的 $n$ 次方的最少运算次数。

【输入格式】

输入数据最后一行为0，表示读入结束；

【样例输入】

1
31
70
91
473
512
811
953
0

【样例输出】

0
6
8
9
11
9
13
12

【数据规模与约定】

对于$30$%的数据，$1≤n≤200$；

对于另外$20$%的数据，$200<n≤1000$；

对于另外$40$%的数据，$1000<n≤6000$；

对于另外$10$%的数据，$40000≤n≤50000$；

输入最多$30$组数据；

【来源】

$zhc$

$cogs$ $3451$ 加强版