Compositions Missing a Sequence

A composition of an integer $n$ is an ordered list of positive integers whose sum is $n$. Two compositions that use the same numbers in a different order count as different, which is what separates compositions from partitions. Written out in full, the compositions of the first few integers are:

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}

For 3, the compositions 1+2 and 2+1 are counted separately. As you may have guessed, an integer $n$ has $2^{n-1}$ compositions.

This problem puts a condition on the numbers a composition uses. A composition misses a set $S$ when no number in the composition belongs to $S$. The compositions of the first few integers that miss the set of even integers are:

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

No odd integer has a composition that misses the set of odd integers, and every composition of an even integer $n$ into even numbers alone pairs off with a composition of $n/2$ multiplied by 2.

Write a program that counts the compositions of $n$ which miss the arithmetic sequence $\{m + ik \mid i = 0, 1, 2, \dots\}$.

The first line contains one integer $P$, the number of data sets ($1 \le P \le 10000$). Each data set is processed the same way and independently of the others.

Each of the next $P$ lines holds one data set. A line contains the data set number $K$, followed by the three space separated integers $n$, $m$ and $k$ ($1 \le n \le 30$, $0 \le m < k < 30$).

Print one line for each data set. The line contains the data set number $K$, a single space, then the number of compositions of $n$ which miss the given sequence.