Digit Sums

Time limit1sMemory limit128 MB

Summary

Count positive integers up to A whose base-B digits add up to C for each query line.

Level: Medium4 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

You are given three positive integers $A$ , $B$ , and $C$ . How many positive integers not greater than $A$ have digits that sum to $C$ when the number is written in base $B$ ?

Input

The input is a series of lines. Each line holds three integers $A$ , $B$ , and $C$ separated by one or more blanks, with $2 \le B \le 100$ and $1 \le A, C \le 10^9$ . All three numbers are given in base 10. A line containing three zeros ends the input and is not processed.

Output

For each input line, print the number of such integers in base 10, one per line.

Examples1

Example 1

Input

100 10 9
100 10 1
750000 2 2
1000000000 10 40
100000000 100 200
0 0 0

Expected output