A. Освещение парка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Парк представляет из себя прямоугольную таблицу состоящую из $$$n$$$ строк и $$$m$$$ столбцов, где клетки таблицы — площади, а границы между клетками — улицы. Также улицами являются внешние границы. Каждая улица имеет длину $$$1$$$. Например, у парка размера $$$n=m=2$$$ всего $$$12$$$ улиц.

Вам поручили разработать план освещения парка. Вы можете ставить фонари в серединах улиц. Фонарь освещает две площади, между которыми он стоит (или только одну площадь, если он стоит на границе парка).

Пример парка размеров: $$$n=4$$$, $$$m=5$$$. Освещенные площади отмечены жёлтым цветом. Обратите внимание, что все улицы имеют длины $$$1$$$. Фонари ставятся в середины улиц. На картинке не все площади освещены.

Семён Сергеевич хочет потратить на освещение наименьшее возможное количество денег, но также хочет чтобы люди по всему парку держали социальную дистанцию. Поэтому он просит вас узнать, какое минимальное количество фонарей понадобится, чтобы осветить все площади.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных записывается одной строкой, содержащей два натуральных числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^4$$$) — размеры парка.

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

Выведите $$$t$$$ ответов на наборы тестовых данных. Каждый ответ должен содержать одно целое число — минимальное количество фонарей для того, чтобы осветить все площади.

Пример
Входные данные
5
1 1
1 3
2 2
3 3
5 3
Выходные данные
1
2
2
5
8
Примечание

Возможное оптимальное расположение фонарей для $$$2$$$-го набора входных данных примера:

Возможное оптимальное расположение фонарей для $$$3$$$-го набора входных данных примера: