A. Таблица MEX
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В один из дней школьник Марк плохо себя вел, поэтому преподаватель Саша вызвал его к доске.

Саша дал Марку таблицу из $$$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$$$-м столбце.

Сашу не интересует, как Марк расставил числа, поэтому он просит его сказать лишь одно число — максимальную сумму MEX по всем строкам и столбцам, которую можно получить.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.

Например:

  • $$$\operatorname{mex}([2,2,1])= 0$$$, так как $$$0$$$ не принадлежит массиву.
  • $$$\operatorname{mex}([3,1,0,1]) = 2$$$, так как $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ нет.
  • $$$\operatorname{mex}([0,3,1,2]) = 4$$$, так как $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ нет.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — количество строк и столбцов в таблице соответственно.

Выходные данные

Для каждого набора входных данных выведите максимальную возможную сумму $$$\operatorname{mex}$$$ по всем строкам и столбцам.

Пример
Входные данные
3
1 1
2 2
3 5
Выходные данные
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$$$.