Коровы вычисляют «жизненный цикл» для каждого номера на своих идентификационных бирках.

Возьмите любое положительное целое число $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