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ⁿ⁻¹ ways to partition a queue of size n.</p>

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.

입력 형식

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).

출력 형식

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

예제 입력

3
10 0 2
15 1 4
28 3 7

예제 출력

55
235
18848806