As vacas estão calculando o «ciclo de vida» de cada número de suas etiquetas de identificação.

Tome qualquer inteiro positivo $N$ ($1 \le N \le 9999$), por exemplo 57, eleve os dígitos ao quadrado e some-os: $5^2+7^2$ resulta em $25 + 49 = 74$. Faça o mesmo procedimento com o resultado 74 para obter o próximo número da sequência, 65. Ao continuar aplicando esse procedimento aos termos da sequência, algum número acaba se repetindo.

Começando com 57, o primeiro número que se repete é 37:

$57, 74, 65, 61,$

A partir daí, a sequência fica presa em um «ciclo de vida»:

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

Se elevarmos os dígitos ao cubo em vez de ao quadrado, a sequência tem um destino semelhante. Escreva um programa que calcule o comprimento da sequência até entrar em um ciclo de vida, dados um inteiro positivo inicial e uma potência $P$ ($1 \le P \le 5$).

Entrada

Uma única linha com dois inteiros $N$ e $P$, separados por um espaço.

Saída

Comprimento da sequência até entrar em um ciclo de vida, sem incluir o primeiro número do ciclo.

Exemplos

Entrada 1

57 2

Saída 1

4

Nota

Detalhes da saída

[Isso corresponde à sequência: $57, 74, 65, 61, 37, \ldots$; 37 é o primeiro número que se repete.]

Créditos do problema: Piele, 2002