# [Solution] Fill The Grid solution codechef

Fill The Grid solution codechef – You have a grid with NN rows and MM columns. You have two types of tiles — one of dimensions 2×22×2 and the other of dimensions 1×11×1.

## [Solution] Fill The Grid solution codechef

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×11×1 tiles used is minimized.

Find the minimum number of 1×11×1 tiles you have to use to fill the grid.

### Input Format

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

### Output Format

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

### Constraints

• 1T1041≤T≤104
• 1N,M1041≤N,M≤104

## [Solution] Fill The Grid solution codechef

4
1 1
4 5
6 8
3 2


### Sample Output 1

1
4
0
2


## [Solution] Fill The Grid solution codechef Explanation

Test case 11: There is only one square in the grid, and it must be filled with a single 1×11×1 tile.

Test case 22: One way of tiling the grid using 1×11×1 tiles exactly 44 times is as follows:

Test case 33: One way of tiling the grid using no 1×11×1 tiles is as follows:

Test case 44: One way of tiling the grid using 1×11×1 tiles exactly twice is: