I. 棋盘

小J面前有一个 $n\times m$ 的棋盘，他手里面还有很多个形如"L"型的拼图，拼图如下图所示：

该拼图可以旋转或反转放入棋盘中

他想问你这个棋盘在拼图不互相重叠的情况下最多能摆多少块拼图。

第一行，一个整数 $t(1\le t \le 100)$，代表数据组数。

对于每组数据，输入一行两个整数 $n,m(1\le n,m \le 10^6)$，分别代表棋盘的长和宽。

对于每组数据，输出一行一个正整数，代表在拼图不互相重叠的情况下棋盘中最多能摆多少块拼图。

输入样例

4
2 3
3 3
1 100
7 5

输出样例

2
2
0
11

样例解释
样例中第二组和第三组数据分别按照如下方式摆放。