给出正整数n,若只能使用乘法或除法，输出使x经过运算（自己乘或除自己，以及乘或除运算过程中产生的中间结果）变成x^n的最少步数
若干行数据，每行一个正整数n，数据以单独成行的0结束
若干行数据，对应每行输入的n所需的步数
1 31 70 91 473 512 811 953 0
0 6 8 9 11 9 13 12
30%数据，n\leq30
100%数据，n\leq1024
100%数据，数字个数k\leq100