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 \le P \le 1\, 000$), 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 \le m \le 100$), followed by a space, followed by the integer, $n$, ($3 \le n \le 10\, 000$), 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.
|Sample Input 1||Sample Output 1|
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