Hide

Problem B
Níulegasti grunnurinn

Languages en is
/problems/niulegastigrunnurinn/file/statement/en/img-0001.jpg
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 \leq n, d \leq 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 $\geq 2$ should be considered.

Output

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

Scoring

Group

Points

Constraints

1

40

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

2

30

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

3

30

No further constraints

Sample Input 1 Sample Output 1
203433 9
3
Sample Input 2 Sample Output 2
48899 4
2