题目描述

Shekhu 有 $N$ 个球。她想把它们分配到一个或多个桶中，并满足以下所有约束条件：

1. 从左到右读取时，桶中的球数必须呈非递减顺序。
2. 最左边的桶必须非空，且最左边桶中的球数必须能被 $D$ 整除。
3. 任意两个桶之间的球数之差（并不仅是相邻桶）必须小于或等于 $2$。

Shekhu 有多少种不同的分配方式？如果从左到右读取桶中球数的列表不同，则认为两种方式不同。

输入格式

输入的第一行给出测试用例的数量 $T$。

接下来有 $T$ 个测试用例。每个测试用例由一行两个整数 $N$ 和 $D$ 组成，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述答案。

3
7 1
7 2
2 4

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

提示

在样例 #1 中，可能的分布为：

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 不是有效的分布，因为 1 和 4 之间的差值大于 2。

在样例 #2 中，可能的分布为：

2 2 3

3 4 不可行，因为第一项不能被 2 整除。

在样例 #3 中，不存在可行的排列。

限制条件

$1 \le T \le 100$。

$1 \le D \le 100$。

小数据集（测试集 1 – 可见）

$1 \le N \le 2000$。

大数据集（测试集 2 – 隐藏）

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成