You have a grid with N rows and M columns. You have two types of tiles — one of dimensions $2 \times 2$ and the other of dimensions $1 \times 1.$ You want to cover the grid using these two types of tiles in such a way that:
Each cell of the grid is covered by exactly one tile; and
The number of $1 \times 1$ tiles used is minimized.

Find the minimum number of $1 \times 1$ tiles you have to use to fill the grid.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of a single line containing two space-separated integers N, M.

------ Output Format ------

For each test case, print on a new line the minimum number of $1 \times 1$ tiles needed to fill the grid.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$1 ≤ N, M ≤ 10^{4}$

----- Sample Input 1 ------
4
1 1
4 5
6 8
3 2

----- Sample Output 1 ------
1
4
0
2

----- explanation 1 ------
Test case $1$: There is only one square in the grid, and it must be filled with a single $1 \times 1$ tile.

Test case $2$: One way of tiling the grid using $1\times 1$ tiles exactly $4$ times is as follows:

Test case $3$: One way of tiling the grid using no $1\times 1$ tiles is as follows:

Test case $4$: One way of tiling the grid using $1\times 1$ tiles exactly twice is:

见题面

见题面