← 返回题目列表

Codeforces · 2057/A

A. 墨西哥表

中文机器翻译题面 查看原题

有一天,男生马克行为不端,老师萨沙把他叫到白板前。

Sasha 给了 Mark 一个包含 $$$n$$$ 行和 $$$m$$$ 列的表。他的任务是在表中排列数字 $$$0, 1, \ldots, n \cdot m - 1$$$(每个数字必须仅使用一次),以使所有行和列的 MEX$$$^{\text{*}}$$$ 之和最大化。更正式地说,他需要最大化 $$$$$$\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}\}),$$$$$$ 其中 $$$a_{i,j}$$$ 是第 $$$i$$$ 行和 $$$j$$$ 列中的数字。

Sasha 对 Mark 如何排列数字不感兴趣,因此他只要求他说出一个数字——所有行和列上可以达到的 MEX 的最大总和。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^9$$$) - 分别是表中的行数和列数。

输出

对于每个测试用例,输出所有行和列中 $$$\operatorname{mex}$$$ 的最大可能总和。

示例

输入 #1

3
1 1
2 2
3 5

输出 #1

2
3
6

注意

在第一个测试用例中,唯一的元素是 $$$0$$$,第一行中的数字 $$$\operatorname{mex}$$$ 与第一列中的数字 $$$\operatorname{mex}$$$ 之和为 $$$\operatorname{mex}(\{0\}) + \operatorname{mex}(\{0\}) = 1 + 1 = 2$$$。

在第二个测试用例中,最优表可能如下所示:

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

然后 $$$\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$$$。