Le mucche stanno calcolando il «ciclo di vita» di ciascun numero sulle loro targhette identificative.

Prendete un intero positivo $N$ ($1 \le N \le 9999$), per esempio 57, elevate al quadrato le cifre e sommatele: $5^2+7^2$ dà $25 + 49 = 74$. Ripetete la procedura sul risultato 74 per ottenere il numero successivo della sequenza, 65. Continuando ad applicare questa procedura ai termini della sequenza, un numero finisce per ripetersi.

Partendo da 57, il primo numero che si ripete è 37:

$57, 74, 65, 61,$

Da quel momento la sequenza rimane intrappolata in un «ciclo di vita»:

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

Se eleviamo le cifre al cubo anziché al quadrato, la sequenza ha una sorte simile. Scrivete un programma che calcoli quanto è lunga la sequenza prima di entrare in un ciclo di vita, dati un intero positivo iniziale e una potenza $P$ ($1 \le P \le 5$).

Input

Una sola riga con due interi $N$ e $P$, separati da uno spazio.

Output

Lunghezza della sequenza fino all’ingresso in un ciclo di vita, senza includere il primo numero del ciclo.

Esempi

Input 1

57 2

Output 1

4

Nota

Dettagli dell’output

[Questo corrisponde alla sequenza: $57, 74, 65, 61, 37, \ldots$; 37 è il primo numero che si ripete.]

Autore del problema: Piele, 2002