The cows are calculating the "life cycle" for each of their identification tag numbers.

Take any positive integer $N$ ($1 \le N \le 9999$), say 57, square the digits and add them up: $5^2+7^2$ to get $25 + 49 = 74$. Now do the same procedure with the result 74 to get the next number in the sequence 65. Continuing to apply this procedure to a sequence of terms eventually repeats one number of the sequence.

When starting with 57, the sequence repeats for the first time with 37:

57, 74, 65, 61,

and from then on the sequence is trapped in a "life cycle":

37, 58, 89, 145, 42, 20, 4, 16, 37, . . .

If we cube the digits instead of squaring them the sequence has a similar fate. Your job is to write a program that computes how long the sequence lasts until it falls into a life cycle given a starting positive integer and a power $P$ ($1 \le P \le 5$).

Input

A single line with two space-separated integers: $N$ and $P$.

Output

Length of the sequence until it enters a life cycle, not including the first number in the cycle.

Examples

Input 1

57 2

Output 1

4

Output Details

[This corresponds to the sequence: 57, 74, 65, 61, 37, ...; 37 is the first number that is repeated.]

Problem credits: Piele, 2002