Partitioning a Queue

Time Limit: 1 Second    Memory Limit: 65536 KB

There are n passengers in a single queue, waiting to enter the airplane. To avoid congestion, the queue should be partitioned into smaller parts. There are several ways to partition the queue. For instance, a queue of size 3 can be partitioned into1+2, 2+1, 1+1+1 or 3. It is easy to prove that there are 2^n-1 ways to partition a queue of size n.

The problem becomes a little complicated, when we are not allowed to use parts whose sizes are in some given set S. For instance, if S is the set of even numbers, a queue of size 4 can be partitioned in 3 ways, namely 1+1+1+1, 1+3 and 3+1. You’re task is to count the number of ways to partition a queue of size n, with an additional condition that the size of no part should be in a given arithmetic sequence {m+ik|i=0, 1,…} for the given m, k.

Input

The first line of the input includes the number of test cases 1≤t≤10000. Each test case consists of three space separated integers n, m, k (1≤n ≤30, 0 ≤ m< k<30).

Output

For each test case, print one line containing the answer to the question

Sample Input

3
10 0 2
15 1 4
28 3 7

Sample Output

55
235
18848806 

Submit

Source: 13th Iran Nationwide Internet Contest - Final