题目描述

CodejamOn 游戏正火热进行中！众多玩家聚集在一个礼堂中，争夺世界冠军。在开幕式上，玩家们将坐在一个由 $R$ 行 $C$ 列组成的座位网格中。

比赛将会非常激烈，玩家们对坐在太多未来对手附近非常敏感！如果某玩家的正左方和正右方都各有一名其他玩家，则该玩家会感到过于拥挤。同样，如果某玩家的正前方和正后方都各有一名其他玩家，该玩家也会感到过于拥挤。

求在不使任何玩家感到过于拥挤的前提下，最多可以坐多少名玩家。

输入格式

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

输出格式

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

3
2 2
2 3
4 1

Case #1: 4
Case #2: 4
Case #3: 3

提示

在样例 #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 完成