수열을 피하는 순서 있는 분할

정수 $n$의 순서 있는 분할은 합이 $n$인 양의 정수를 차례로 나열한 것이다. 쓰인 수가 같아도 순서가 다르면 서로 다른 분할로 센다. 이 점이 순서 있는 분할과 순서를 무시하는 분할을 가른다. 작은 정수의 순서 있는 분할을 모두 적으면 다음과 같다.

1: {1}
2: {1+1, 2}
3: {1+1+1, 1+2, 2+1, 3}
4: {1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1, 4}

3의 분할에서 1+2와 2+1은 서로 다르게 센다. 짐작한 대로 $n$의 순서 있는 분할은 모두 $2^{n-1}$개다.

이 문제에서는 분할에 쓰이는 수에 조건을 건다. 분할에 나오는 어떤 수도 집합 $S$에 들어 있지 않으면, 그 분할은 $S$를 피한다고 한다. 짝수 전체의 집합을 피하는 분할을 작은 정수부터 적으면 다음과 같다.

1: {1}
2: {1+1}
3: {1+1+1, 3}
4: {1+1+1+1, 1+3, 3+1}

홀수 전체의 집합을 피하는 분할은 홀수에 하나도 없고, 짝수만으로 이루어진 짝수 $n$의 분할은 $n/2$의 분할에 2를 곱한 것과 하나씩 짝지어진다.

등차수열 $\{m + ik \mid i = 0, 1, 2, \dots\}$를 피하는 $n$의 순서 있는 분할이 몇 개인지 세는 프로그램을 작성한다.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다 ($1 \le P \le 10000$). 각 데이터 집합은 서로 독립이고, 모두 같은 방법으로 처리한다.

이어지는 $P$개의 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄에는 데이터 집합 번호 $K$와 세 정수 $n$, $m$, $k$가 공백으로 구분되어 주어진다 ($1 \le n \le 30$, $0 \le m < k < 30$).

데이터 집합마다 한 줄을 출력한다. 그 줄에는 데이터 집합 번호 $K$, 공백 하나, 주어진 수열을 피하는 $n$의 순서 있는 분할의 개수를 차례로 적는다.