CF2057A MEX Table

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.

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.

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

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 $ .