|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||15||11||9||81.818%|
A partition of an integer n is a set of positive integers which sum to n, typically written in descending order. For example:
10 = 4+3+2+1
A partition is m-ary if each term in the partition is a power of m. For example, the 3-ary partitions of 9 are:
9 3+3+3 3+3+1+1+1 3+1+1+1+1+1+1 1+1+1+1+1+1+1+1+1
Write a program to find the number of m-ary partitions of an integer n.
The first line of input contains a single decimal integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input. The line contains the data set number, K, followed by the base of powers, m, (3 <= m <= 100), followed by a space, followed by the integer, n, (3 <= n <= 10000), for which the number of m-ary partitions is to be found.
For each data set there is one line of output. The output line contains the data set number, K, a space, and the number of m-ary partitions of n. The result should fit in a 32-bit unsigned integer.
5 1 3 9 2 3 47 3 5 123 4 7 4321 5 97 9999
1 5 2 63 3 75 4 144236 5 111