Description

奶牛们用“生命周期”来标记它们的身份。取一个整数N (1 <= N <= 9999)，如57，将每个数字的平方加在一起：5^2 + 7^2=25 + 49 = 74，现在对74做同样的操作得到65，一直做到在产生的整数序列中有一个数重复出现。当以57开始时，这个序列第一次出现37，因为从57，74，65，61，然后序列进入“生命周期”：37，58，89，145，42，20，4，16，37，… 如果我们用立方来代替刚才的平方也会有相似的情况，你的任务就是编程对给出的整数和幂P (1 <= P <= 5)，计算何时出现生命周期的序列长度。

Input

每组一行两个整数：N和P

Output

出现生命周期时的序列长度，不包括第一个生命周期数

Sample

Input

57 2

Output

3

Hint

上例序列：57，74，65，61，37，…，37就是第1个重复的数