奶牛們正在計算各自身分標牌編號的「生命週期」。

取任意正整數 $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