题目描述

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 翻译

样例

2
2 2
1 3

4
3