시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 3 3 100.000%

문제

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

힌트