m-ary Partitions

A partition of an integer $n$ is a collection of positive integers whose sum is $n$, usually written in descending order. For example:

10 = 4+3+2+1

A partition is m-ary if every term in it is a power of $m$. The 3-ary partitions of 9 are these five:

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 that counts the m-ary partitions of an integer $n$.

The first line contains the number of data sets $P$ ($1 \le P \le 1000$). The data sets are independent and are all processed the same way.

Each data set is one line holding three integers separated by spaces: the data set number $K$ ($1 \le K \le 1000$), the base of the powers $m$ ($3 \le m \le 100$), and the integer $n$ ($3 \le n \le 10000$) whose m-ary partitions are to be counted. The data set numbers come from the input and are not guaranteed to be sorted.

The number of m-ary partitions of $n$ always fits in a 32-bit unsigned integer.

Print one line per data set, in the order the data sets appear in the input. Each line holds the data set number $K$ read from the input, one space, and the number of m-ary partitions of $n$.