| Технокубок 2022 - Отборочный Раунд 2 |
|---|
| Закончено |
У Васи есть красный клетчатый прямоугольник размера $$$n \times m$$$. Но он ему не нравится. Поэтому Вася несколько раз разрежет исходный или любой другой, получившийся в ходе разрезания, прямоугольник на две части вдоль одной из линий сетки. Он может сделать эту операцию сколько угодно раз.
В результате он получит набор прямоугольников. Прямоугольники $$$1 \times 1$$$ запрещены.
Еще Вася умеет красить клеточки в синий цвет. Он хочет, чтобы каждый прямоугольник из набора был раскрашен так, что соседние по стороне клетки имели разные цвета.
Какое минимальное количество клеточек Васе придется покрасить?
В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.
Единственная строка описания каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^4$$$, $$$n \cdot m \geq 2$$$).
Для каждого набора входных данных выведите единственное целое число — минимальное количество клеток, которое придется покрасить Васе.
4 1 3 2 2 2 5 3 5
1 2 4 5
Приведенные ниже картинки показывают, как прямоугольник может быть разрезан, и какие клетки могут быть покрашены синим после этого.
В первом наборе входных данных:
Во втором наборе входных данных:
В третьем наборе входных данных:
В четвертом наборе входных данных:
