#216627. [GKS 2016 #E] Partioning Number

Shekhu has balls. She wants to distribute them among one or more buckets in a way that satisfies all of these constraints:

1. The numbers of balls in the buckets must be in non-decreasing order when read from left to right.
2. The leftmost bucket must be non-empty and the number of balls in the leftmost bucket must be divisible by .
3. The difference (in number of balls) between any two buckets (not just any two adjacent buckets) must be less than or equal to .

How many different ways are there for Shekhu to do this? Two ways are considered different if the lists of numbers of balls in buckets, reading left to right, are different.

The first line of the input gives the number of test cases, .

test cases follow. Each test case consists of one line with two integers and , as described above.

For each test case, output one line containing Case #x: y, where is the test case number (starting from ) and is the answer, as described above.

样例输入 1

3
7 1
7 2
2 4

样例输出 1

Case #1: 10
Case #2: 1
Case #3: 0

In sample case #1, the 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

Note that 1 2 4 is not a valid distribution, since the difference between 1 and 4 is more than 2.

In sample case #2, the possible distributions are:

2 2 3

3 4 is not possible, since the first term is not divisible by 2.

In sample case #3, no possible arrangement exists.

Limits

.

.

Small dataset (Test set 1 - Visible)

.

Large dataset (Test set 2 - Hidden)

.