You are given two positive integers $A$ and $B$. Find the number of pairs of positive integers $(X, Y)$ such that $1 \le X \le A$, $1 \le Y \le B$ and $X + Y$ is even.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $A$ and $B$.

-----Output-----
For each test case, print a single line containing one integer ― the number of valid pairs.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le A, B \le 10^9$

-----Subtasks-----
Subtask #1 (10 points): $A, B \le 10$
Subtask #2 (10 points): $A, B \le 1,000$
Subtask #3 (80 points): original constraints

-----Example Input-----
4
1 1
2 3
4 6
8 9

-----Example Output-----
1
3
12
36

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
try:
	t = int(input())
	while t > 0:
		[a, b] = [int(x) for x in input().split()]
		if a == 1 and b == 1:
			print(1)
			continue
		if a % 2 == 0:
			o1 = a // 2
			e1 = a // 2
		else:
			o1 = a // 2 + 1
			e1 = a // 2
		if b % 2 == 0:
			o2 = b // 2
			e2 = b // 2
		else:
			o2 = b // 2 + 1
			e2 = b // 2
		print(e1 * e2 + o1 * o2)
		t -= 1
except:
	pass


import math
t = int(input())
for i in range(t):
	(a, b) = tuple(map(int, input().split()))
	ea = a // 2
	eb = b // 2
	oa = math.ceil(a / 2)
	ob = math.ceil(b / 2)
	print(ea * eb + oa * ob)


T = int(input())
while T > 0:
	(x, y) = list(map(int, input().split()))
	c_e_a = 0
	c_e_b = 0
	c_o_a = 0
	c_o_b = 0
	if x == 1 and y == 1:
		print(1)
		break
	for i in range(1, x + 1):
		if i & 1:
			c_o_a += 1
		else:
			c_e_a += 1
	for j in range(1, y + 1):
		if j & 1:
			c_o_b += 1
		else:
			c_e_b += 1
	print(c_e_a * c_e_b + c_o_a * c_o_b)
	T -= 1


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	count = 0
	if a % 2 != 0:
		even_x = a // 2
		odd_x = a // 2 + 1
	else:
		even_x = a // 2
		odd_x = a // 2
	if b % 2 != 0:
		even_y = b // 2
		odd_y = b // 2 + 1
	else:
		even_y = b // 2
		odd_y = b // 2
	count = even_x * even_y + odd_x * odd_y
	print(count)


def sub(a, b):
	aeven = int(a / 2)
	beven = int(b / 2)
	if a % 2 == 0:
		if b % 2 == 0:
			sum = a * beven
		else:
			sum = b * aeven
	elif b % 2 == 0:
		sum = beven * (aeven + (aeven + 1))
	else:
		sum = beven * aeven + (beven + 1) * (aeven + 1)
	return sum
t = int(input())
for i in range(t):
	(n1, n2) = map(int, input().split(' '))
	print(sub(n1, n2))


def esum(a, b):
	count = 0
	for i in range(1, a + 1):
		for j in range(1, b + 1):
			if i % 2 == 0 and j % 2 == 0:
				count += 1
			if i % 2 == 1 and j % 2 == 1:
				count += 1
	return count
z = int(input())
while z > 0:
	(x, y) = list(map(int, input().split(' ')))
	print(esum(x, y))
	z -= 1


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	count = 0
	for i in range(1, a + 1):
		for j in range(1, b + 1):
			if (i + j) % 2 == 0:
				count += 1
	print(count)


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	x = min(a, b)
	y = max(a, b)
	count = 0
	for i in range(1, x + 1):
		for j in range(1, y + 1):
			if (i + j) % 2 == 0:
				count += 1
	print(count)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a & 1 == 1 and b & 1 == 1:
		print(a * b // 2 + 1)
	else:
		print(a * b // 2)


try:
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		if a % 2 != 0 and b % 2 != 0:
			print(a * b // 2 + 1)
		else:
			print(a * b // 2)
except:
	pass


for i in range(int(input())):
	(A, B) = list(map(int, input().split()))
	c = 0
	for j in range(1, A + 1):
		for k in range(1, B + 1):
			if (j + k) % 2 == 0:
				c = c + 1
	print(c)


for i in range(int(input())):
	(a, b) = map(int, input().split(' '))
	evenA = a // 2
	evenB = b // 2
	oddA = (a + 1) // 2
	oddB = (b + 1) // 2
	pairs = evenA * evenB + oddA * oddB
	print(pairs)


n = int(input())
l = []
for i in range(0, n):
	(a, b) = map(int, input().split())
	count = 0
	for j in range(0, a):
		for k in range(0, b):
			if (j + k) % 2 == 0:
				count += 1
	l.append(count)
for i in l:
	print(i)


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	c = []
	d = []
	(p, q) = (0, 0)
	(x, y) = (0, 0)
	for i in range(1, a + 1):
		c.append(i)
	for i in range(1, b + 1):
		d.append(i)
	for i in range(len(c)):
		if c[i] % 2 == 0:
			p += 1
		else:
			q += 1
	for i in range(len(d)):
		if d[i] % 2 == 0:
			x += 1
		else:
			y += 1
	print(p * x + q * y)