Description

你是一名房东，拥有一栋由 $R \times C$ 个公寓组成的大楼，每个公寓是一个单位正方形单元格，四面都有墙。你打算将其中 $N$ 个公寓出租，每个公寓恰好住一名租客，其余公寓保持空置。不幸的是，所有潜在租客都很吵，因此每当有两个被占用的公寓共享一面墙（仅限于共享墙，而不是仅仅是角），大楼的“不愉快值”就会增加 $1$。例如，在一个 $2 \times 2$ 的大楼中，如果每个公寓都被占用，则有四面墙被相邻租客共享，因此大楼的“不愉快值”为 $4$。

如果你以最优方式安排这 $N$ 名租客入住，最小的不愉快值是多少？

Input Format

输入的第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含三个用空格分隔的整数：$R$、$C$ 和 $N$。

Output Format

对于每个测试用例，输出一行，格式为 “Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该大楼可能的最小不愉快值。

4
2 3 6
4 1 2
3 3 8
5 2 0

Case #1: 7
Case #2: 0
Case #3: 8
Case #4: 0

Hint

样例解释

在第 1 个样例中，每个房间都被租客占据，所有 7 面内部墙都有租客在两侧。

在第 2 个样例中，有多种方式可以安排两名租客，使他们不共享墙。其中一种方式如下图所示。

在第 3 个样例中，最优策略是将 8 名租客安排成一个环，中间的公寓空着。

下图展示了样例 1-3 的示意图。每一面红色的墙都会增加一分不愉快值。

样例说明

• $1 \leq T \leq 1000$。
• $0 \leq N \leq R \times C$。

小数据集（12 分）

• 时间限制：240 5 秒。
• $1 \leq R \times C \leq 16$。

大数据集（15 分）

• 时间限制：480 10 秒。
• $1 \leq R \times C \leq 10000$。

由 ChatGPT 4.1 翻译