CF1358A.Park Lighting

Due to the coronavirus pandemic, city authorities obligated citizens to keep a social distance. The mayor of the city Semyon wants to light up Gluharniki park so that people could see each other even at night to keep the social distance.

The park is a rectangular table with $n$ rows and $m$ columns, where the cells of the table are squares, and the boundaries between the cells are streets. External borders are also streets. Every street has length $1$. For example, park with $n=m=2$ has $12$ streets.

You were assigned to develop a plan for lighting the park. You can put lanterns in the middle of the streets. The lamp lights two squares near it (or only one square if it stands on the border of the park).

The park sizes are: $n=4$, $m=5$. The lighted squares are marked yellow. Please note that all streets have length $1$. Lanterns are placed in the middle of the streets. In the picture not all the squares are lit.

Semyon wants to spend the least possible amount of money on lighting but also wants people throughout the park to keep a social distance. So he asks you to find the minimum number of lanterns that are required to light all the squares.

由于新冠疫情，城市当局要求市民保持社交距离。城市市长谢苗希望点亮格鲁哈尔尼基公园，以便人们即使在夜间也能彼此看见，从而保持社交距离。

公园是一个具有 $n$ 行 $m$ 列的矩形表格，其中表格的每个单元格为正方形，单元格之间的边界为街道，外部边界也均为街道。每条街道长度均为 $1$。例如，当 $n = m = 2$ 时，公园共有 $12$ 条街道。

你被委派制定公园的照明方案。你可以在街道的中点处安装灯笼。一盏灯笼可照亮其两侧相邻的两个正方形（若灯笼位于公园边界上，则仅能照亮一侧的一个正方形）。

公园尺寸为：$n = 4$，$m = 5$。图中被照亮的正方形标为黄色。请注意，所有街道长度均为 $1$，灯笼均置于街道中点。图中并非所有正方形均被照亮。

谢苗希望以最少的资金投入完成公园照明，同时确保公园内所有人员均能保持社交距离。因此，他请你找出能够照亮全部正方形所需的最少灯笼数量。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is a line containing two integers $n$, $m$ ($1 \le n, m \le 10^4$) — park sizes.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入中测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例是一行，包含两个整数 $n$、$m$（$1 \le n, m \le 10^4$）—— 公园的尺寸。

Print $t$ answers to the test cases. Each answer must be a single integer — the minimum number of lanterns that are required to light all the squares.

输出 $t$ 个测试用例的答案。每个答案必须是一个整数——即照亮所有方格所需的最少灯笼数量。

Possible optimal arrangement of the lanterns for the $2$-nd test case of input data example:

Possible optimal arrangement of the lanterns for the $3$-rd test case of input data example:

第 2 个输入数据样例测试用例的灯笼可能最优排列：

第 3 个输入数据样例测试用例的灯笼可能最优排列：