整数 $n$ 的一个划分（partition）是指一组正整数，它们的和为 $n$，通常按降序排列。例如：

$10 = 4+3+2+1$

如果划分中的每一项都是 $m$ 的幂，则称该划分为 $m$-ary 划分。例如，9 的 3-ary 划分有：

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

编写一个程序，求整数 $n$ 的 $m$-ary 划分的数量。

输入格式

输入的第一行包含一个十进制整数 $P$ ($1 \le P \le 1000$)，表示随后数据组的数量。每组数据应被独立且相同地处理。

每组数据由单行输入组成。该行包含数据组编号 $K$，随后是幂的底数 $m$ ($3 \le m \le 100$)，接着是一个空格，最后是整数 $n$ ($3 \le n \le 10000$)，即需要求其 $m$-ary 划分数量的整数。

输出格式

对于每组数据，输出一行。输出行包含数据组编号 $K$、一个空格以及 $n$ 的 $m$-ary 划分数量。结果应能存入 32 位无符号整数中。

样例

样例输入 1

5
1 3 9
2 3 47
3 5 123
4 7 4321
5 97 9999

样例输出 1

1 5
2 63
3 75
4 144236
5 111