Partitioning a Queue

Time limit2sMemory limit512 MB

Summary

Count compositions of n whose parts avoid the arithmetic progression m, m+k, m+2k, with n up to 30 and up to 10000 test cases.

Level: Medium4 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

n passengers stand in one queue, waiting to board an airplane. To keep the gate from getting crowded, the queue is cut into consecutive parts. A queue of size 3 can be cut as 1+2, 2+1, 1+1+1 or 3. Two cuts that use the same part sizes in a different order count as different, so a queue of size n has $2^{n-1}$ partitions.

The problem gets harder once some part sizes are forbidden. For given integers m and k, no part may have a size that appears in the arithmetic sequence $m, m+k, m+2k, \dots$ . For example, with m = 0 and k = 2 every even size is forbidden, so a queue of size 4 has only 3 partitions: 1+1+1+1, 1+3 and 3+1.

Every part has size at least 1. Count the partitions of a queue of size n under this rule.

Input

The first line contains the number of test cases t ( $1 \le t \le 10000$ ). Each of the next t lines contains three integers n, m, k separated by spaces ( $1 \le n \le 30$ , $0 \le m < k < 30$ ).

Output

For each test case, print the number of partitions on its own line.

Examples2

Example 1
Input
```
3
10 0 2
15 1 4
28 3 7
```
Expected output
```
55
235
18848806
```
Example 2
Input
```
2
4 0 2
3 0 4
```
Expected output
```
3
4
```