由于冠状病毒大流行,市政府有义务公民保持社交距离。谢苗市市长希望点亮格鲁哈尼基公园,以便人们即使在晚上也能看到彼此,以保持社交距离。
公园是一个矩形表格,有 $$$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 测试用例的灯笼可能的最佳排列: