Coding Minds

#### Start

2020-11-16 12:30 AKST

## Coding Minds

#### End

2020-11-23 12:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -68 days 12:43:02

167:30:00

0:00:00

# Problem Hm-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.

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