给定一个n×m 的棋盘，初始为红色，可以将它沿格线切割成若干个面积大于1的小长方形。
现需要选取小长方形中一些1×1 的格子（即单位格），并把它涂成蓝色。要求对于任意小长方形中任意两个相邻单位格颜色不相同。请你帮忙计算一下，最少需要涂多少次？

第一行为整数T,表示有T(1≤T≤1000)组测试样例。
每组测试样例仅包含两个整数n与m (1≤n,m≤30000, n*m≥2).

对于每组测试样例输出一个整数，表示最少涂色次数。

4
1 3
2 2
2 5
3 5

1
2
4
5

每组测试样例的切割与涂色方案如下：

测试样例1：

测试样例2：

测试样例3：

测试样例4：