Description

Given 3 positive integers, $n$, $b$, and $s$, generate the next $n$ numbers in base $b$ starting with $s$ in the given base. We guarantee that the base $b$ will be between 2 and 9 inclusive. We guarantee that $s$ is a valid number in base $b$. Find the base 10 value for the number of times the largest possible digit in the given base is found among all of the digits in the numbers generated.

Input Format

There will be three integers representing the number of values to be found ($n$), the base to be used ($b$) between 2 and 9 inclusive, and the starting value ($s$) in the base given which will be no longer than 16 digits.

Output Format

For each set of 3 input values, output a base 10 number representing the number of times the largest digit in the inputted base occurs in the sequence of numbers generated.

Explanation

Example: If $n=15, b=8, s=2$: The base 8 numbers generated are 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20. The largest possible digit in base 8 is 7. 7 occurs 2 times (once in the number 7, and once in the number 17).

15 8 2

2

20 3 12

21

25 5 324

24

13 9 1652

1

45 2 1111011

170