A. MEX Table
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, the schoolboy Mark misbehaved, so the teacher Sasha called him to the whiteboard.

Sasha gave Mark a table with $$$n$$$ rows and $$$m$$$ columns. His task is to arrange the numbers $$$0, 1, \ldots, n \cdot m - 1$$$ in the table (each number must be used exactly once) in such a way as to maximize the sum of MEX$$$^{\text{∗}}$$$ across all rows and columns. More formally, he needs to maximize $$$$$$\sum\limits_{i = 1}^{n} \operatorname{mex}(\{a_{i,1}, a_{i,2}, \ldots, a_{i,m}\}) + \sum\limits_{j = 1}^{m} \operatorname{mex}(\{a_{1,j}, a_{2,j}, \ldots, a_{n,j}\}),$$$$$$ where $$$a_{i,j}$$$ is the number in the $$$i$$$-th row and $$$j$$$-th column.

Sasha is not interested in how Mark arranges the numbers, so he only asks him to state one number — the maximum sum of MEX across all rows and columns that can be achieved.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

For example:

  • $$$\operatorname{mex}([2,2,1])= 0$$$, since $$$0$$$ does not belong to the array.
  • $$$\operatorname{mex}([3,1,0,1]) = 2$$$, since $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
  • $$$\operatorname{mex}([0,3,1,2]) = 4$$$, since $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.
Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the number of rows and columns in the table, respectively.

Output

For each test case, output the maximum possible sum of $$$\operatorname{mex}$$$ across all rows and columns.

Example
Input
3
1 1
2 2
3 5
Output
2
3
6
Note

In the first test case, the only element is $$$0$$$, and the sum of the $$$\operatorname{mex}$$$ of the numbers in the first row and the $$$\operatorname{mex}$$$ of the numbers in the first column is $$$\operatorname{mex}(\{0\}) + \operatorname{mex}(\{0\}) = 1 + 1 = 2$$$.

In the second test case, the optimal table may look as follows:

$$$3$$$$$$0$$$
$$$2$$$$$$1$$$

Then $$$\sum\limits_{i = 1}^{n} \operatorname{mex}(\{a_{i,1}, a_{i,2}, \ldots, a_{i,m}\}) + \sum\limits_{j = 1}^{m} \operatorname{mex}(\{a_{1,j}, a_{2,j}, \ldots, a_{n,j}\}) = \operatorname{mex}(\{3, 0\}) + \operatorname{mex}(\{2, 1\})$$$ $$$+ \operatorname{mex}(\{3, 2\}) + \operatorname{mex}(\{0, 1\}) = 1 + 0 + 0 + 2 = 3$$$.