Coloring Rectangles

题意翻译

给定一个 $n\times m$ 的棋盘，你要将它沿格线切割成若干个小长方形（面积不为 1 ）。 你要将小长方形中一些 $1\times1$ 的格子（下文称作单位格）涂色，保证对于任意小长方形，任意两个相邻单位格不同色。 求最小涂色次数。 $$ 1\le n,m\le 3\times10^4,nm\ge1 $$

题目描述

David was given a red checkered rectangle of size $ n \times m $ . But he doesn't like it. So David cuts the original or any other rectangle piece obtained during the cutting into two new pieces along the grid lines. He can do this operation as many times as he wants. As a result, he will get a set of rectangles. Rectangles $ 1 \times 1 $ are forbidden. David also knows how to paint the cells blue. He wants each rectangle from the resulting set of pieces to be colored such that any pair of adjacent cells by side (from the same piece) have different colors. What is the minimum number of cells David will have to paint?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^3 $ ) — the number of test cases. The next lines contain descriptions of test cases. The only line of each test case contains two integers $ n $ , $ m $ ( $ 1 \leq n, m \leq 3 \cdot 10^4 $ , $ n \cdot m \geq 2 $ ).

输出格式

For each test case print a single integer — the minimum number of cells David will have to paint blue.

输入输出样例

输入样例 #1

4
1 3
2 2
2 5
3 5

输出样例 #1

1
2
4
5

说明

The following pictures show how the initial rectangle can be split and cells colored blue. In the first test case: In the second test case: In the third test case: In the fourth test case: