Las vacas están calculando el «ciclo de vida» de cada número de sus etiquetas de identificación.

Toma cualquier entero positivo $N$ ($1 \le N \le 9999$), por ejemplo 57, eleva sus dígitos al cuadrado y súmalos: $5^2+7^2$ da $25 + 49 = 74$. Aplica el mismo procedimiento al resultado 74 para obtener el siguiente número de la secuencia, 65. Al continuar aplicando el procedimiento a los términos de la secuencia, algún número acaba repitiéndose.

Al empezar con 57, el primer número que se repite es 37:

$57, 74, 65, 61,$

A partir de entonces la secuencia queda atrapada en un «ciclo de vida»:

$37, 58, 89, 145, 42, 20, 4, 16, 37, \ldots$

Si elevamos los dígitos al cubo en lugar de al cuadrado, la secuencia tiene un destino similar. Tu tarea es escribir un programa que calcule la longitud de la secuencia hasta entrar en un ciclo de vida, dados un entero positivo inicial y una potencia $P$ ($1 \le P \le 5$).

Entrada

Una línea con dos enteros $N$ y $P$, separados por un espacio.

Salida

Longitud de la secuencia hasta entrar en un ciclo de vida, sin incluir el primer número del ciclo.

Ejemplos

Entrada 1

57 2

Salida 1

4

Nota

Detalles de la salida

[Esto corresponde a la secuencia: $57, 74, 65, 61, 37, \ldots$; 37 es el primer número que se repite.]

Autor del problema: Piele, 2002