Description

你将和你的小弟弟玩一个简化版的“战舰”游戏。游戏的棋盘是一个有 $R$ 行 $C$ 列的矩形网格。在游戏开始时，你会闭上眼睛，并且直到游戏结束都不会睁开。你的小弟弟会在棋盘上放置一艘 $1 \times W$ 的矩形战舰，且只能水平放置。战舰必须完全放在棋盘内，每个船格正好占据棋盘的一个格子，且不能旋转。

游戏的每一回合，你可以指定棋盘上的一个格子，你的小弟弟会告诉你这个格子是否命中（即该格子是否被战舰占据）或未命中。（你的小弟弟不会告诉你命中的是战舰的哪一部分——只会告诉你该格子是否有船。）你有完美的记忆力，能记录下他给你的所有信息。当你已经指出了战舰占据的所有格子时，游戏结束（战舰被击沉），你的得分是你所用的回合数。你的目标是让得分尽可能小。

虽然战舰一旦放置后理论上不应移动，但你知道你的小弟弟会作弊，只要新的位置依然是水平且完全在棋盘内，并且与他之前给你的所有信息一致，他就会随时移动战舰。例如，在一个 $1 \times 4$ 的棋盘上放一艘 $1 \times 2$ 的战舰，他可以最初把船放在最左边的两列。如果你第一次猜 $(1,2)$，他可以偷偷把船移到最右边的两列，并告诉你 $(1,2)$ 是未命中。如果你下一步猜 $(1,3)$，他就不能再说未命中并把船移回原来的位置了，因为那样会和他之前说的 $(1,2)$ 是未命中矛盾。

不仅如此，你知道你的小弟弟会作弊，他也知道你知道。如果你们都采取最优策略（你想让得分最小，他想让得分最大），你无论如何都能保证的最小得分是多少？

Input Format

输入的第一行是测试用例数 $T$。接下来的 $T$ 行，每行包含三个用空格分隔的整数 $R$、$C$ 和 $W$，分别表示棋盘的行数、列数和战舰的宽度。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你能保证的最小得分。

3
1 4 2
1 7 7
2 5 1

Case #1: 3
Case #2: 7
Case #3: 10

Hint

样例解释

在第 1 个用例中，棋盘有一行四列，战舰占据一行两列。一种最优策略是你先猜 $(1,2)$：

如果你的小弟弟说命中，那么 $1 \times 2$ 的战舰的另一个格子只能在 $(1,1)$ 或 $(1,3)$，你只需分别猜这两个格子。如果你正好猜中了另一个格子，你的小弟弟会把船移到 $(1,2)$ 依然命中但你猜的那个格子未命中的位置。注意即使你已经命中，小弟弟依然可以移动船，只要不和之前的信息矛盾。

如果你的小弟弟说未命中，那么唯一剩下的可能就是船在 $(1,3)$ 和 $(1,4)$，你只需猜这两个格子。

所以无论小弟弟怎么做，在你猜 $(1,2)$ 后，最多再用两步就能结束，总共三步。

而且三步是最优的，因为你不可能保证用两步完成：无论你第一步猜哪里，小弟弟都可以把船移到剩下的 $1 \times 2$ 区域，并说未命中。你无法在只剩一步的情况下击沉还未被命中的船。

在第 2 个用例中，战舰完全填满棋盘，所以小弟弟只有一种放法。你只需把所有格子都猜一遍。

在第 3 个用例中，小弟弟总能把 $1 \times 1$ 的战舰移到你没猜过的格子，所以你必须把 10 个格子都猜一遍，最后一个才会命中并击沉战舰。

限制条件

• $1 \leq W \leq C$。

小数据范围

• 时间限制：5 秒。
• $T = 55$。
• $R = 1$。
• $1 \leq C \leq 10$。

大数据范围

• 时间限制：10 秒。
• $1 \leq T \leq 100$。
• $1 \leq R \leq 20$。
• $1 \leq C \leq 20$。

由 ChatGPT 4.1 翻译