I. 棋盘
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

Input

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

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

Output

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

Example
Input
4
2 3
3 3
1 100
7 5
Output
2
2
0
11
Note

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