계산기

학교에서 제공한 계산기를 비밀 코드로 업그레이드할 수 있다는 소문이 돌고 있다. 계산기 화면에 비밀 kålnami 코드를 표시한 다음 등호를 누르면 여러 비밀 수학 기능이 잠금 해제된다고 한다.

친구가 kålnami 코드가 무엇인지 알아냈지만, 그 코드를 아무 방식으로나 계산기에 입력할 수 있는 것은 아니라고 알려 주었다. 처음에 계산기에는 $0$이 표시되어 있다. 그다음 다음 연산을 수행할 수 있다:

• 표시된 수에 $M$을 곱한다.

• $k$이 $0 \leq k \leq M-1$을 만족할 때, 임의의 수 $k$을 표시된 수에 더한다.

다행히 친구는 $M$의 값도 알아냈다. 이 복잡한 과정은 가능한 한 적은 연산을 수행해야만 작동한다. 따라서 kålnami 코드와 $M$의 값이 주어졌을 때 필요한 최소 연산 횟수를 구해야 한다.

채점

제출한 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 테스트 그룹의 점수를 받으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$20$| $M=3, N \leq 10$.

$2$ |$20$| $M=2$

$3$ |$20$| $N \leq 10^5$

$4$ |$40$| 추가 제약 조건이 없다.

입력의 첫째 줄에는 kålnami 코드의 값인 정수 $N$ ($1 \leq N \leq 10^9$)이 주어진다.

다음 줄에는 위에서 의미를 설명한 숫자 $M$ ($2 \leq M \leq 9$)이 주어진다.

계산기에 kålnami 코드 $N$을 표시하는 데 필요한 최소 연산 횟수를 나타내는 정수 하나를 출력한다.

예제 1에서 최소 연산 횟수로 코드를 입력하는 한 가지 방법은 다음과 같다:

• $+1$

• $\times 2$

• $\times 2$

예제 2에서 최적해는 다음 연산을 수행하는 것이다:

• $+1$

• $\times 3$

• $\times 3$

• $+2$

• $\times 3$