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 $b$ will be between 2 and 9 inclusive. We guarantee that $s$ is a valid number in base $b$. Find the base 10 sum of all of the digits in the numbers generated.

Input Format

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

Output Format

For each set of 3 input values, output a base 10 number representing the sum of all of the digits generated.

Explanation

If $n=15$, $b=8$, and $s=2$, the base 8 numbers generated are 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20. The base 10 sum of all of their digits is 65.

15 8 2

65

20 3 12

64

25 5 324

189

13 9 1652

212

45 2 1111011

170