m진 분할

정수 $n$의 분할은 합이 $n$인 양의 정수 모음이고, 보통 내림차순으로 쓴다. 예를 들면 다음과 같다.

10 = 4+3+2+1

분할에 들어가는 항이 모두 $m$의 거듭제곱이면 이 분할을 m진 분할이라고 한다. 9의 3진 분할은 다음 다섯 가지다.

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진 분할이 몇 개인지 세는 프로그램을 작성하라.

첫 줄에 데이터 세트의 개수 $P$ ($1 \le P \le 1000$)가 주어진다. 데이터 세트는 서로 독립이고 모두 같은 방법으로 처리한다.

각 데이터 세트는 한 줄이며, 공백으로 구분한 정수 세 개로 이루어진다. 차례대로 데이터 세트 번호 $K$ ($1 \le K \le 1000$), 거듭제곱의 밑 $m$ ($3 \le m \le 100$), m진 분할의 개수를 셀 정수 $n$ ($3 \le n \le 10000$)이다. 데이터 세트 번호는 입력에서 읽는 값이고, 오름차순이라는 보장은 없다.

$n$의 m진 분할 개수는 항상 32비트 부호 없는 정수 범위에 들어간다.

데이터 세트마다 한 줄씩, 입력에 나온 순서대로 출력한다. 각 줄에는 입력에서 읽은 데이터 세트 번호 $K$, 공백 하나, $n$의 m진 분할 개수를 차례대로 쓴다.