奶牛们正在计算各自身份标牌编号的“生命周期”。

取任意正整数 $N$（$1 \le N \le 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, \ldots$

如果将各位数字立方而不是平方，序列也有类似的结局。你的任务是编写一个程序，在给定起始正整数和幂次 $P$（$1 \le P \le 5$）的情况下，计算序列在进入生命周期之前有多长。

输入格式

一行包含两个以空格分隔的整数 $N$ 和 $P$。

输出格式

序列进入生命周期之前的长度，不包括周期中的第一个数。

样例

输入格式 1

57 2

输出格式 1

4

说明

输出细节

[这对应于序列：$57, 74, 65, 61, 37, \ldots$；37 是第一个重复出现的数。]

题目作者：Piele，2002