P16589 [GKS 2016 #D] Sitting

**CodejamOn** 游戏正火热进行中！众多玩家聚集在一个礼堂中，争夺世界冠军。在开幕式上，玩家们将坐在一个由 $R$ 行 $C$ 列组成的座位网格中。 比赛将会非常激烈，玩家们对坐在太多未来对手附近非常敏感！如果某玩家的正左方和正右方都各有一名其他玩家，则该玩家会感到过于拥挤。同样，如果某玩家的正前方和正后方都各有一名其他玩家，该玩家也会感到过于拥挤。 求在不使任何玩家感到过于拥挤的前提下，最多可以坐多少名玩家。

输入的第一行给出测试用例的数量 $T$；接下来有 $T$ 个测试用例。每个测试用例由一行两个整数 $R$ 和 $C$ 组成，表示礼堂中座位的行数和列数。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是题目描述中所能坐下的最多玩家数量。

在样例 #1 中，我们可以填满所有座位，且没有玩家会感到过于拥挤。 在样例 #2 中，每行有三个座位。我们不能在一行中放三个玩家，因为这样会使中间的玩家感到过于拥挤。一种最优解是填满前两列的所有座位，总共可坐 $4$ 名玩家。 在样例 #3 中，一种最优解是填满前两行和最后一行，总共可坐 $3$ 名玩家。 ### 限制条件 $1 \le T \le 100$。 **小数据集（测试集 1 – 可见）** $1 \le R \le 5$。 $1 \le C \le 5$。 **大数据集（测试集 2 – 隐藏）** $1 \le R \le 100$。 $1 \le C \le 100$。 翻译由 DeepSeek V4 Pro 完成