你是一位房东，拥有一栋 $R \times C$ 网格状的公寓楼；每间公寓都是一个有四面墙的单位正方形单元。你想要将其中 $N$ 间公寓出租给租户，每间公寓恰好住一名租户，其余公寓保持空置。不幸的是，你所有的潜在租户都很吵闹，因此每当有两间已出租的公寓共享一面墙（不仅仅是共享一个角）时，这会为大楼增加 1 点“不快乐值”。例如，一个 $2 \times 2$ 的大楼中，如果每间公寓都住满了人，那么相邻租户之间共有 4 面共享墙，因此该大楼的不快乐值为 4。

如果你以最优方式安置这 $N$ 名租户，大楼的最小不快乐值是多少？

样例

输入格式 1

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

输出格式 1

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

说明

在样例 1 中，每个房间都住有租户，所有 7 面内部墙的两侧都有租户。

在样例 2 中，有多种放置两名租户的方法，使得他们不共享墙壁。其中一种如下图所示。

在样例 3 中，最优策略是将 8 名租户围成一圈放置，留下中间的公寓空置。

以下是样例 1-3 的示意图。每一面红色的墙都会增加 1 点不快乐值。