← 返回题目列表

Codeforces · 1358/A

A. 公园照明

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

由于冠状病毒大流行,市政府有义务公民保持社交距离。谢苗市市长希望点亮格鲁哈尼基公园,以便人们即使在晚上也能看到彼此,以保持社交距离。

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

您被指派制定公园照明计划。你可以在街道中央放灯笼。灯照亮它附近的两个方格(如果它位于公园边界,则仅照亮一个方格)。

公园大小为:$$$n=4$$$,$$$m=5$$$。亮起的方块标记为黄色。请注意,所有街道的长度均为 $$$1$$$。灯笼被放置在街道中央。在图中,并非所有方块都被点亮。

Semyon 希望在照明上花费尽可能少的钱,但也希望整个公园的人们保持社交距离。所以他要求你找出照亮所有方格所需的最少灯笼数量。

输入

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

每个测试用例都是一行,包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 10^4$$$) — 公园大小。

输出

打印测试用例的 $$$t$$$ 答案。每个答案必须是一个整数——点亮所有方块所需的最小灯笼数量。

示例

输入 #1

5
1 1
1 3
2 2
3 3
5 3

输出 #1

1
2
2
5
8

注意

输入数据示例的 $$$2$$$-nd 测试用例的灯笼可能的最佳排列:

输入数据示例的 $$$3$$$-rd 测试用例的灯笼可能的最佳排列: