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

在游戏的每一轮中，你指定棋盘上的一个格子，你的弟弟会告诉你这是命中（船只占据的格子之一）还是未命中。（你的弟弟不会告诉你船只的哪一部分被击中，只会告诉你你指定的格子是否有船只的一部分。）你拥有完美的记忆力，可以记录他给出的所有信息。一旦你指定了船只占据的所有格子，游戏结束（船只沉没），你的得分即为所用的轮数。你的目标是最小化你的得分。

虽然船只一旦放置就不应该移动，但你知道你的弟弟是个淘气鬼，他计划通过在任何时候改变船只的位置来作弊，只要船只保持水平且完全位于棋盘内，并且新位置与他目前给出的所有信息一致即可。例如，对于 $1 \times 4$ 的棋盘和 $1 \times 2$ 的船只，你的弟弟最初可以将船只放置在覆盖最左侧两列的位置。如果你的第一次猜测是第 1 行第 2 列，他可以选择秘密地将船只移动到最右侧两列，并告诉你 (1, 2) 是未命中。但如果你接下来的猜测是 (1, 3)，他就不能再说这也是未命中并将船只移回原位，因为这与他之前关于 (1, 2) 的说法不一致。

不仅你知道你的弟弟会作弊，他也知道你知道。如果你们双方都采取最优策略（你为了最小化得分，他为了最大化得分），无论你的弟弟如何行动，你所能保证达到的最低得分是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含三个空格分隔的整数 $R$、$C$ 和 $W$：棋盘的行数和列数，以及船只的宽度。

输出格式

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

数据范围

$1 \le W \le C$。

小数据集

$T = 55$。 $R = 1$。 $1 \le C \le 10$。

大数据集

$1 \le T \le 100$。 $1 \le R \le 20$。 $1 \le C \le 20$。

样例

样例输入 1

3
1 4 2
1 7 7
2 5 1

样例输出 1

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

说明

在样例 1 中，棋盘有 1 行 4 列，船只占据 1 行 2 列。一种最优策略是你从指定格子 (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 个格子，直到最后一个才最终命中（并立即击沉船只）。