CF1484A.Prison Break

Michael is accused of violating the social distancing rules and creating a risk of spreading coronavirus. He is now sent to prison. Luckily, Michael knows exactly what the prison looks like from the inside, especially since it's very simple.

The prison can be represented as a rectangle $a\times b$ which is divided into $ab$ cells, each representing a prison cell, common sides being the walls between cells, and sides on the perimeter being the walls leading to freedom. Before sentencing, Michael can ask his friends among the prison employees to make (very well hidden) holes in some of the walls (including walls between cells and the outermost walls). Michael wants to be able to get out of the prison after this, no matter which cell he is placed in. However, he also wants to break as few walls as possible.

Your task is to find out the smallest number of walls to be broken so that there is a path to the outside from every cell after this.

迈克尔被指控违反社交距离规定，存在传播新冠病毒的风险，因此被送进监狱。幸运的是，迈克尔对监狱内部的结构了如指掌，尤其是因为这座监狱的结构极为简单。

该监狱可表示为一个 $a\times b$ 的矩形，被划分为 $ab$ 个单元格，每个单元格代表一间囚室；相邻单元格之间的公共边为囚室间的墙壁，而矩形边界上的边则为通向自由的外墙。在宣判前，迈克尔可以请求身为狱警的朋友（在监狱工作人员中）在某些墙壁（包括囚室之间的内墙以及最外层的外墙）上凿出（隐蔽性极强的）洞。迈克尔希望：无论自己被关押在哪一间囚室，都能在凿洞之后成功逃出监狱。同时，他还希望凿开的墙壁数量尽可能少。

你的任务是求出满足上述条件所需凿开的最少墙壁数量，即：使得从每一个囚室出发均存在一条通往监狱外部的路径。

The first line contains a single integer $t$ ($1\leq t\leq 100$) — the number of test cases.

Each of the following $t$ lines contains two integers $a$ and $b$ ($1\leq a, b\leq 100$), representing a corresponding test case.

第一行包含一个整数 $t$（$1\leq t\leq 100$），表示测试用例的数量。

接下来的 $t$ 行中，每行包含两个整数 $a$ 和 $b$（$1\leq a, b\leq 100$），表示对应的测试用例。

For each test case print the single integer on a separate line — the answer to the problem.

对于每个测试用例，在单独一行中输出一个整数——即该问题的答案。

Some possible escape plans for the example test cases are shown below. Broken walls are shown in gray, not broken walls are shown in black.

以下为示例测试用例的一些可能的逃生方案。被破坏的墙壁以灰色显示，未被破坏的墙壁以黑色显示。