Given 3 positive integers A, B and C, find how many positive integers less than or equal to A, when expressed in base B, have digits which sum to C.

입력 형식

Input will consist of a series of lines, each containing three integers, A, B and C, 2 ≤ B ≤ 100, 1 ≤ A, C ≤ 1,000,000,000. The numbers A, B and C are given in base 10 and are separated by one or more blanks. The input is terminated by a line containing three zeros.

출력 형식

Output will be the number of numbers, for each input line (it must be given in base 10).

예제 입력

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

예제 출력

10
3
189
45433800
666303