Partitioning Balls into Buckets

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

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

How many ways are there? Two ways count as different when the lists of bucket sizes, read from left to right, differ.

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

Each of the next $T$ lines contains one test case: two integers $N$ and $D$ separated by a space.

Limits

• $1 \le T \le 100$
• $1 \le D \le 100$
• $1 \le N \le 2000$

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.

For $N = 7$ and $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 does not count, because the difference between 1 and 4 is more than 2.

For $N = 7$ and $D = 2$ the only possible distribution is 2 2 3. The distribution 3 4 is excluded because its first bucket holds 3 balls, which is not divisible by 2.

For $N = 2$ and $D = 4$ no distribution exists.