Description

经营一家糖果店可不容易！你需要优化各种各样的事情。最近你在销售一种非常受欢迎的糖果，名叫 Whizboppers。这种糖果很快就会变质，因此有如下特性：

• 你必须每天早上从供应商那里购买新的 Whizboppers。
• 你必须用当天早上从供应商那里买来的盒子出售 Whizboppers。

你可以从供应商那里订购任意整数克数的 Whizboppers 盒子。

每天最多有 $k$ 位顾客光临你的商店，并且从第一个顾客开始，他们会选择一个整数数量的美分来购买 Whizboppers：在 $1$ 到 $C$ 美分之间（包含 $1$ 和 $C$）。你将以每克 $1$ 美分的价格出售 Whizboppers；因此，如果某人想花 $4$ 美分，你就会给他正好 $4$ 克的糖果。你可以通过给他一个 $4$ 克的盒子，或者两个 $2$ 克的盒子和两个 $1$ 克的盒子来实现。

你需要订购最少数量的盒子，以保证无论每个人点多少克，你都能满足所有顾客的需求。

注意：当某个人选择购买多少糖果时，你已经知道之前的人买了多少，但你不知道后面的人会买多少。

例如，如果每天最多有 $2$ 位顾客，每人最多花 $2$ 美分（$k=2$，$C=2$），你可以从供应商那里购买四个 $1$ 克的盒子。但你可以做得更好：如果你买两个 $1$ 克的盒子和一个 $2$ 克的盒子，你也能满足所有顾客。如下所示：

第一位顾客   发出的盒子     第二位顾客   发出的盒子
------------------------------------------------
  2 美分      1 个 2 克盒子    2 美分       2 个 1 克盒子
                                 1 美分        1 个 1 克盒子
  -------------------------------------------------------
  1 美分      1 个 1 克盒子    2 美分       1 个 2 克盒子
                                 1 美分        1 个 1 克盒子

无论第一位顾客点多少，你都能分配盒子，使得第二位顾客仍然能得到正确数量的糖果。因此对于 $k=2, C=2$，你每天只需准备 $3$ 个盒子即可满足任意顺序的订单。

Input Format

输入的第一行是测试用例数 $T$。接下来的 $T$ 行，每行包含两个整数 $k$ 和 $C$，分别表示每天最多的顾客数和每位顾客最多花费的美分数。

Output Format

对于每个测试用例，输出一行，格式为 “Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你每天需要订购的最少盒子数。

4
1 5
2 2
10 3
2 50

Case #1: 3
Case #2: 3
Case #3: 19
Case #4: 11

Hint

样例解释

在第一个样例中，你可以购买一个 $1$ 克盒子和两个 $2$ 克盒子。在第二个样例中，你可以购买两个 $1$ 克盒子和一个 $2$ 克盒子。

数据范围

• $1 \leq T \leq 100$。

小数据集（7 分，测试集 1 - 可见）

• $1 \leq k \leq 20$。
• $1 \leq C \leq 3$。

大数据集（20 分，测试集 2 - 隐藏）

• $1 \leq k \leq 1000$。
• $1 \leq C \leq 10^{12}$。

由 ChatGPT 4.1 翻译