P13409 [GCJ 2010 Finals] Candy Store

经营一家糖果店可不容易！你需要优化各种各样的事情。最近你在销售一种非常受欢迎的糖果，名叫 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$ 个盒子即可满足任意顺序的订单。

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

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

**样例解释** 在第一个样例中，你可以购买一个 $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 翻译