CF1484A Prison Break

Michael 因违反社交距离规定并造成传播新冠病毒的风险而被指控。他现在被送进了监狱。幸运的是，Michael 非常清楚监狱内部的样子，尤其是因为它非常简单。 监狱可以表示为一个 $a\times b$ 的矩形，被划分为 $ab$ 个牢房，每个牢房代表一个监狱单元，相邻牢房之间的公共边为牢房之间的墙，矩形外围的边为通向自由的外墙。在被判刑之前，Michael 可以请求他在监狱工作的朋友在一些墙上打洞（这些洞会被隐藏得很好），包括牢房之间的墙和最外层的墙。Michael 希望无论他被关在哪个牢房，都能逃出监狱。然而，他也希望打破的墙尽可能少。 你的任务是计算出，为了让每个牢房都能有一条通向外部的路径，最少需要打破多少面墙。

第一行包含一个整数 $t$（$1\leq t\leq 100$），表示测试用例的数量。 接下来的 $t$ 行，每行包含两个整数 $a$ 和 $b$（$1\leq a, b\leq 100$），分别表示每个测试用例的参数。

对于每个测试用例，输出一个整数，表示问题的答案，每个答案占一行。

下图展示了一些示例测试用例的可能逃脱方案。被打破的墙用灰色表示，未被打破的墙用黑色表示。   由 ChatGPT 4.1 翻译