Problem B
Níulegasti grunnurinn

Image from flickr.com

Jörmunrekur was playing around with writing some numbers in different bases. He started by trying $203433$. His favourite number is nine, so he doesn’t particularly care for this number. But if he writes it in base $16$ it becomes $31AA9$ which is a clear improvement since one of the digits is now nine. If he writes it in base $12$ it becomes $99889$ which is even better. Great even, three nines, you could hardly ask for something better. Or can you?

Input

The input is a single line containing two integers $1\le n,d\le {10}^{18}$. The integer $n$ is the number to be written out in some base and the integer $d$ is the digit Jörmunrekur wants to maximize the occurrences of. Only bases $\ge 2$ should be considered.

Output

Print how often $d$ can appear at most if the right base is chosen.

Scoring

203433 9

3

48899 4

2