소들은 각 식별 표지 번호의 "생애 주기"를 계산하고 있다.

임의의 양의 정수 $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