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:

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
for t in range(int(input())):
	(n, m) = map(int, input().split())
	if n % 2 != 0 and m % 2 != 0:
		print(n + m - 1)
	elif n % 2 != 0 and m % 2 == 0:
		print(m)
	elif n % 2 == 0 and m % 2 != 0:
		print(n)
	else:
		print(0)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	if N % 2 and M % 2:
		print(N + M - 1)
	elif not N % 2 and M % 2:
		print(N)
	elif not M % 2 and N % 2:
		print(M)
	else:
		print(0)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	A = N // 2 * (M // 2)
	print(N * M - A * 4)


for t in range(int(input())):
	(rows, cols) = map(int, input().split())
	if rows % 2 != 0 and cols % 2 != 0:
		print(rows + cols - 1)
	elif rows % 2 == 0 and cols % 2 != 0:
		print(rows)
	elif cols % 2 == 0 and rows % 2 != 0:
		print(cols)
	else:
		print(0)


for i in range(int(input())):
	(m, n) = map(int, input().split())
	if m & 1 == 0 and n & 1 == 0:
		print(0)
	elif m & 1 == 0 and n & 1 == 1:
		print(m)
	elif m & 1 == 1 and n & 1 == 0:
		print(n)
	else:
		print(m + n - 1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 2 == 0 and b % 2 == 0:
		print(0)
	elif a % 2 == 0:
		print(a)
	elif b % 2 == 0:
		print(b)
	elif a % 2 != 0 and b % 2 != 0:
		print(a * b - (a - 1) * (b - 1))


test = int(input())
for i in range(test):
	(a, b) = map(int, input().split())
	if a % 2 != 0 and b % 2 != 0:
		print(a + b - 1)
	elif a % 2 != 0 and b % 2 == 0:
		print(b)
	elif a % 2 == 0 and b % 2 != 0:
		print(a)
	else:
		print(0)


t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	if N % 2 == 0 and M % 2 == 1 or (N % 2 == 1 and M % 2 == 0):
		if N % 2 == 1:
			print(M)
		elif M % 2 == 1:
			print(N)
		else:
			print(0)
	elif N % 2 == 1 and M % 2 == 1:
		print(N + M - 1)
	else:
		print(0)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	res = 0
	if x % 2 != 0:
		res = y
	if res != 0 and y % 2 != 0:
		res += x - 1
	elif y % 2 != 0:
		res += x
	print(res)


a = int(input(''))
for t in range(0, a):
	(x, y) = map(int, input('').split())
	if x % 2 == 0 and y % 2 == 0:
		print(0)
	elif x == y == 1:
		print(1)
	elif x % 2 != 0 and y % 2 == 0:
		print(y)
	elif x % 2 == 0 and y % 2 != 0:
		print(x)
	elif x % 2 != 0 and y % 2 != 0:
		print(x + y - 1)


for i in range(int(input())):
	line = input()
	words = line.split()
	n = int(words[0])
	m = int(words[1])
	a = n // 2 * (m // 2)
	print(n * m - a * 4)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	N2 = N
	M2 = M
	ones = 0
	if N % 2 == 0 and M % 2 == 0:
		print(0)
	elif N * M == 1:
		print(1)
	else:
		if N % 2 != 0 and M % 2 != 0:
			N2 -= 1
			M2 -= 1
			ones += M2 + N
		elif N % 2 != 0:
			ones += M
		elif M % 2 != 0:
			ones += N
		print(ones)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	print(N * M - N // 2 * (M // 2) * 4)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(n + m - 1 if n % 2 != 0 and m % 2 != 0 else m if n % 2 != 0 and m % 2 == 0 else n if n % 2 == 0 and m % 2 != 0 else 0)


def min_one_by_one_tiles(n, m):
	if n % 2 != 0 and m % 2 != 0:
		return n + m - 1
	elif n % 2 != 0 and m % 2 == 0:
		return m
	elif n % 2 == 0 and m % 2 != 0:
		return n
	else:
		return 0
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(min_one_by_one_tiles(n, m))


Test = int(input())
for Cases in range(Test):
	(Rows, Columns) = map(int, input().split())
	if Rows % 2 != 0 and Columns % 2 != 0:
		print(Rows + Columns - 1)
	elif Rows % 2 == 0 and Columns % 2 != 0:
		print(Rows)
	elif Rows % 2 != 0 and Columns % 2 == 0:
		print(Columns)
	else:
		print(0)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	print(n % 2 * m + m % 2 * n - n % 2 * m % 2)
	t -= 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	print(n % 2 * m + m % 2 * n - n % 2 * (m % 2))


def fillingrid(x):
	mx = max(x)
	k = 0
	while mx - 2 >= 0:
		k += 1
		mx -= 2
	k *= min(x) // 2
	reqtiles = x[0] * x[1] - 4 * k
	return reqtiles
test_cases = int(input())
l = []
for i in range(test_cases):
	l.append([int(i) for i in input().split()])
for o in l:
	print(fillingrid(o))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	if n % 2 != 0 and x % 2 != 0:
		print(n + x - 1)
	elif n % 2 == 0 and x % 2 != 0:
		print(n)
	elif n % 2 != 0 and x % 2 == 0:
		print(x)
	else:
		print(0)


goals = int(input())
for distractions in range(goals):
	(life, wife) = map(int, input().split())
	if life % 2 != 0 and wife % 2 != 0:
		print(life + wife - 1)
	elif life % 2 != 0 and wife % 2 == 0:
		print(wife)
	elif life % 2 == 0 and wife % 2 != 0:
		print(life)
	else:
		print(0)


def grid():
	(n, m) = map(int, input().split())
	d = n % 2
	c = m % 2
	if d == 0 and c == 0:
		print(0)
	elif d != 0 and c == 0:
		print(m)
	elif d == 0 and c != 0:
		print(n)
	else:
		e = n + m - 1
		print(e)
t = int(input())
for i in range(t):
	grid()


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x % 2 == 0 and y % 2 == 0:
		print(0)
	elif x % 2 != 0 and y % 2 != 0:
		print(x + y - 1)
	elif x % 2 == 0:
		print(x)
	else:
		print(y)


t = int(input())
for i in range(t):
	(r, c) = map(int, input().split())
	if r % 2 == 0 and c % 2 == 0:
		print(0)
	elif r % 2 != 0 and c % 2 != 0 and (r == c):
		print(r * 2 - 1)
	elif r % 2 != 0 and c % 2 != 0:
		print(r + c - 1)
	elif r % 2 != 0 and c % 2 == 0:
		print(c)
	elif r % 2 == 0 and c % 2 != 0:
		print(r)


t = int(input())
for i in range(t):
	l = input()
	w = l.split()
	n = int(w[0])
	m = int(w[1])
	a = n // 2 * (m // 2)
	print(n * m - a * 4)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 2 == 0 and b % 2 == 0:
		print(0)
	else:
		k = int(a / 2) * int(b / 2) * 4
		print(a * b - k)


t = int(input())
for _ in range(t):
	line = input()
	words = line.split()
	n = int(words[0])
	m = int(words[1])
	a = n // 2 * (m // 2)
	print(n * m - a * 4)