아홉이 가장 많이 나오는 진법

이미지 출처: flickr.com

Jörmunrekur는 몇몇 수를 서로 다른 진법으로 표기해 보며 놀고 있었다. 그는 예시로 $203433$부터 시작해 보았다. Jörmunrekur가 가장 좋아하는 수는 아홉이므로, 그는 이 수가 별로 특별하지 않다고 생각한다. 하지만 이를 밑이 $16$인 진법으로 표기하면 $31AA9$이 되며, 여기에는 아홉이 하나 있으므로 곧바로 더 나아진다. 그러나 이를 밑이 $12$인 진법으로 표기하면 $99889$이 된다. 이는 훌륭하다. 아홉이 세 개나 있으니, 이보다 더 좋은 것을 바라기는 어려울 것이다. 과연 그럴까?

채점

그룹 | 점수 | 제한

1      |   40   |  $1 \leq n, d \leq 10^6$

2      |   30   |  $1 \leq n, d \leq 10^{12}$

3      |   30   |  추가 제한 없음

입력은 두 정수 $1 \leq n, d \leq 10^{18}$를 포함하는 한 줄로 주어진다. 정수 $n$은 어떤 진법으로 표기해야 할 수이고, 수 $d$는 Jörmunrekur가 그 표기에서 가장 많이 나타나기를 바라는 수이다. 밑이 적어도 $2$인 진법만 고려해야 한다.

알맞은 밑을 선택했을 때 $d$이 최대 몇 번 나타날 수 있는지 출력한다.