Problem F
m-ary Partitions

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$.

Input

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.

Output

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