Partitioning Number (Large)

Shekhu has $N$ balls. She wants to distribute them among one or more buckets so that all of the following conditions hold.

1. Reading the buckets from left to right, the numbers of balls are in non-decreasing order.
2. The leftmost bucket is not empty, and the number of balls in it is divisible by $D$.
3. For any two buckets, not only for two adjacent ones, the difference between their numbers of balls is at most 2.

In how many different ways can Shekhu do this? Two ways are different if the lists of ball counts, read from left to right, differ.

The first line contains the number of test cases $T$.

Each of the next $T$ lines contains two integers $N$ and $D$.

Limits

• $1 \le T \le 100$
• $1 \le D \le 100$
• $1 \le N \le 10^5$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of ways. The answer can exceed the range of a 32-bit integer.

In the first test case of example 1 ($N = 7$, $D = 1$) the 10 possible distributions are:

• 1 1 1 1 1 1 1
• 1 1 1 1 1 2
• 1 1 1 1 3
• 1 1 1 2 2
• 1 2 2 2
• 1 1 2 3
• 1 3 3
• 2 2 3
• 3 4
• 7

1 2 4 is not a valid distribution, because the difference between 1 and 4 is greater than 2.

In the second test case of example 1 ($N = 7$, $D = 2$) the only possible distribution is 2 2 3. 3 4 fails because its first term is not divisible by 2.

In the third test case of example 1 ($N = 2$, $D = 4$) no distribution exists.