由于新冠疫情，市政府要求市民保持社交距离。谢苗市长希望点亮格卢哈尔尼基公园，让人们即使在夜晚也能见面，以保持社交距离。

公园是一个矩形表格，$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$测试用例的答案。每个答案必须是一个整数——点亮所有方格所需的最少灯笼数量。

注释

输入数据$2$测试用例中灯笼可能的最优排列方式示例：

输入数据$3$测试用例中灯笼可能的最优排列方式示例：

样例

5
1 1
1 3
2 2
3 3
5 3

1
2
2
5
8