The Problem

袁源喜欢跑步,他每天给自己定个目标要跑m米,一米也不能多,一米也不能少(他是怎么精确测量的?).他跑步有个习惯,中途会停下来休息,但是每次连续跑的路程必须是一个自然数(1,2,3......)的k次方(2<=k<=n).如当n=3时,连续跑的路程可以是:1(1^2),4(2^2),8(2^3),9(3^2),16(4^2),25(5^2),27(3^3)...。现在请你来帮帮他计算怎样安排跑步的过程,才能让中途休息的次数最少.

输入

每一行有两个数:m和n(1<=m<=50000,2<=n<=5).中间用一个空格分开.m=n=0 标志输入的结束,并且这组数据不包括在需要计算的数据中.

输出

对应于每一行输入,输出可能的最少休息次数.

样例输入

1 2
5 2
8 3
0 0

样例输出

0
1
0


袁源 2003.4