Solve the programming task below in a Python markdown code block.
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: