David was given a red checkered rectangle of size $n \times m$. But he doesn't like it. So David cuts the original or any other rectangle piece obtained during the cutting into two new pieces along the grid lines. He can do this operation as many times as he wants.

As a result, he will get a set of rectangles. Rectangles $1 \times 1$ are forbidden.

David also knows how to paint the cells blue. He wants each rectangle from the resulting set of pieces to be colored such that any pair of adjacent cells by side (from the same piece) have different colors.

What is the minimum number of cells David will have to paint?


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The next lines contain descriptions of test cases.

The only line of each test case contains two integers $n$, $m$ ($1 \leq n, m \leq 3 \cdot 10^4$, $n \cdot m \geq 2$).


-----Output-----

For each test case print a single integer — the minimum number of cells David will have to paint blue.


-----Examples-----

Input
4
1 3
2 2
2 5
3 5
Output
1
2
4
5


-----Note-----

The following pictures show how the initial rectangle can be split and cells colored blue.

In the first test case:

In the second test case:

In the third test case:

In the fourth test case:

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
T = int(input())
for case in range(T):
	(n, m) = map(int, input().split())
	s = n * m
	if s % 3 == 2:
		res = s // 3 + 1
	else:
		res = s // 3 + s % 3
	print(res)


for s in [*open(0)][1:]:
	(n, m) = sorted(map(int, s.split()))
	k = n % 3
	l = m % 3
	k *= l + 3 * (m > 3 == k * l + 2)
	print((n * m - k) // 3 + k // 2)


for s in [*open(0)][1:]:
	(n, m) = map(int, s.split())
	print(0 - -n * m // 3)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(n * m // 3 + (n * m % 3 > 0))


n = int(input())
for i in range(n):
	(n, m) = map(int, input().split())
	k = n * m
	if k % 3 == 1:
		print(k // 3 + 1)
	elif k % 3 == 2:
		print(k // 3 + 1)
	else:
		print(k // 3)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	x = n // 3 * m
	x += n % 3 * (m // 3)
	if n % 3 * (m % 3) == 0:
		print(x)
	if n % 3 * (m % 3) == 2 or n % 3 * (m % 3) == 1:
		print(x + 1)
	if n % 3 * (m % 3) == 4:
		print(x + 2)


import math
for _ in range(int(input())):
	(u, v) = map(int, input().split())
	ans = math.ceil(u * v / 3)
	print(ans)


T = int(input())
while T:
	T -= 1
	(x, y) = map(int, input().split())
	if not x % 3:
		print(x // 3 * y)
	elif not y % 3:
		print(y // 3 * x)
	else:
		ans = x // 3 * y
		ans += y // 3 * (x % 3)
		ans += min(x % 3, y % 3)
		print(ans)


def solve():
	(a, b) = [int(i) for i in input().split()]
	res = 0
	while a > 2 or b > 2:
		if a > 2 and b > 2:
			if a % 3 <= b % 3:
				res += a // 3 * b
				a %= 3
			else:
				res += a * (b // 3)
				b %= 3
		elif b <= 2:
			res += a // 3 * b
			a %= 3
		elif a <= 2:
			res += a * (b // 3)
			b %= 3
	res += min(a, b)
	print(res)
t = int(input())
for i in range(t):
	solve()


N = int(input())
for i in range(N):
	A = input().split()
	n = int(A[0])
	m = int(A[1])
	if m % 3 != 0:
		a = m * (n // 3) + n % 3 * (1 + m // 3)
	else:
		a = m * (n // 3) + n % 3 * (m // 3)
	if n % 3 != 0:
		b = n * (m // 3) + m % 3 * (1 + n // 3)
	else:
		b = n * (m // 3) + m % 3 * (n // 3)
	print(min(a, b))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	n = n * m
	if n % 3 == 1:
		n = n - 4
		ans += 2
	ans += n // 3 + n % 3 // 2
	print(ans)


from math import ceil
a = int(input())
for i in range(a):
	(n, m) = map(int, input().split())
	print(ceil(n * m / 3))


n = int(input())
res = []

def rect(r, c):
	if r == 0 or c == 0:
		return 0
	if r < 3 and c < 3:
		if r < 2 or c < 2:
			return 1
		return 2
	if c < 3:
		return c * (r // 3) + rect(c, r % 3)
	return r * (c // 3) + rect(r, c % 3)
for i in range(n):
	arr = [int(i) for i in input().split()]
	res.append(rect(arr[0], arr[1]))
for i in res:
	print(i)


import sys
input = sys.stdin.readline
t = int(input())

def getAns(n, m):
	if n == 1:
		if m == 2:
			return 1
		else:
			ans = 0
			ans = int(m / 3)
			if m % 3 == 2 or m % 3 == 1:
				ans += 1
			return ans
	elif m == 2:
		return 2
	else:
		ans = n * int(m / 3)
		a = n
		b = m % 3
		if b == 0:
			return ans
		else:
			return ans + getAns(min(a, b), max(a, b))
while t > 0:
	n = [int(x) for x in input().split(' ')]
	m = n[1]
	n = n[0]
	if n > m:
		(n, m) = (m, n)
	if n == 1:
		if m == 2:
			print(1)
		else:
			ans = 0
			ans = int(m / 3)
			if m % 3 == 2 or m % 3 == 1:
				ans += 1
			print(ans)
	elif m == 2:
		print(2)
	else:
		ans = getAns(n, m)
		print(ans)
	t -= 1


n = int(input())
answer = []
for i in range(n):
	(a, b) = map(int, input().split())
	if a * b % 3 == 0:
		answer.append(a * b // 3)
	elif a * b % 3 != 0:
		answer.append(a * b // 3 + 1)
for i in range(n):
	print(answer[i])


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	if a * b % 3 == 0:
		print(a * b // 3)
	else:
		print(a * b // 3 + 1)


def main():
	n = int(input())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	col_3 = 0
	for i in range(n):
		col_3 = 0
		if l[i][0] % 3 == 0:
			col_3 += l[i][0] / 3 * l[i][1]
		elif l[i][1] % 3 == 0:
			col_3 += l[i][1] / 3 * l[i][0]
		else:
			if l[i][0] < l[i][1]:
				(l[i][0], l[i][1]) = (l[i][1], l[i][0])
			col_3 += l[i][0] // 3 * l[i][1]
			col_3 += l[i][0] % 3 * (l[i][1] // 3)
			if l[i][0] % 3 == 2 and l[i][1] % 3 == 2:
				col_3 += 2
			else:
				col_3 += 1
		print(int(col_3))
main()


for i in range(int(input())):
	(x, y) = map(int, input().split())
	out1 = 0
	n = y // 3
	out1 += n * x
	z = x // 3 + int(x % 3 != 0)
	out1 += z * (y % 3)
	(x, y) = (y, x)
	out = 0
	n = y // 3
	out += n * x
	z = x // 3 + int(x % 3 != 0)
	out += z * (y % 3)
	print(min(out, out1))


from math import gcd
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	res = 0
	if n > m:
		(n, m) = (m, n)
	res += n // 3 * m
	n = n % 3
	if n == 1:
		res += (m + 2) // 3
	elif n == 2:
		res += int(2 * (m + 1) / 3)
	print(res)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	r = 3 * (m // 3 * (n // 3)) + m % 3 * (n // 3) + n % 3 * (m // 3) + min(m % 3, n % 3)
	print(r)


t = int(input())
for _ in range(t):
	res = 0
	(n, m) = map(int, input().split())
	if n < m:
		(n, m) = (m, n)
	if n % 3 == 0 or m % 3 == 0:
		res = m * n // 3
	elif n % 3 == 1:
		res = n // 3 * m + m // 3
		if m % 3 > 0:
			res += 1
	elif n % 3 == 2:
		res = m * (n // 3) + 2 * (m // 3) + m % 3
	print(res)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(n * (m // 3) + n // 3 * (m % 3) + int(math.ceil(n % 3 * (m % 3) / 2)))


t = int(input())

def sol(n, m):
	if n >= 3:
		q = n // 3
		return q * m + sol(n % 3, m)
	elif n == 0:
		return 0
	else:
		q = m // 3
		r = m - 3 * q
		if r == 2:
			return n * (q + 1)
		if r == 1:
			return n * q + 1
		if r == 0:
			return n * q
for _ in range(t):
	(n, m) = map(int, input().split())
	if m < n:
		(n, m) = (m, n)
	print(sol(n, m))


n = int(input())
for i in range(n):
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	k = n * m // 3
	if n * m % 3 == 0:
		print(k)
	elif n // 3 * m + m // 3 * (n % 3) + m % 3 < m // 3 * n + n // 3 * (m % 3) + n % 3:
		if n * m - (n // 3 * m + m // 3 * (n % 3) + m % 3) < n // 3 * m + m // 3 * (n % 3) + m % 3:
			print(n * m - (n // 3 * m + m // 3 * (n % 3) + m % 3))
		else:
			print(n // 3 * m + m // 3 * (n % 3) + m % 3)
	elif n * m - (m // 3 * n + n // 3 * (m % 3) + n % 3) < m // 3 * n + n // 3 * (m % 3) + n % 3:
		print(n * m - (m // 3 * n + n // 3 * (m % 3) + n % 3))
	else:
		print(m // 3 * n + n // 3 * (m % 3) + n % 3)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	if a % 3 < b % 3:
		f = a
		t = b
	else:
		f = b
		t = a
	if f % 3 == 0:
		print(f // 3 * t)
	elif f % 3 == 1:
		print(f // 3 * t + t // 3 + 1)
	else:
		print(f // 3 * t + (t // 3 + 1) * 2)


t = int(input())
all_tr = []
while t > 0:
	x = input()
	all_tr.append(x)
	t -= 1
for i in all_tr:
	summ = 1
	numbers = str(i).split(' ')
	for x in numbers:
		summ *= int(x)
	print(int(summ // 3 if summ % 3 == 0 else summ // 3 + 1))


t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	if n > m:
		(n, m) = (m, n)
	if m * n % 3 == 0:
		print(m * n // 3)
	else:
		k = m // 3 * n + m % 3 * (n // 3)
		m %= 3
		n %= 3
		if m * n == 4:
			print(k + 2)
		else:
			print(k + 1)


def func(n, m):
	if n == 1 and m == 1:
		return 1
	if n == 1:
		if m % 3 == 0:
			return m // 3
		else:
			return m // 3 + 1
	elif m == 1:
		if n % 3 == 0:
			return n // 3
		else:
			return n // 3 + 1
	elif m % 3 == 0 and n % 3 == 0:
		return min(n * (m // 3), m * (n // 3))
	elif m % 3 == 0 and n % 3 != 0:
		return min(n * (m // 3), m * (n // 3 + 1))
	elif m % 3 != 0 and n % 3 == 0:
		return min(n * (m // 3 + 1), m * (n // 3))
	else:
		return min(n * (m // 3 + 1), m * (n // 3 + 1))
t = int(input())
while t:
	(n, m) = map(int, input().split())
	ans = 0
	ans += func(n - n % 3, m - m % 3)
	ans += func(n % 3, m - m % 3)
	ans += func(n - n % 3, m % 3)
	ans += func(n % 3, m % 3)
	print(ans)
	t -= 1


def less(n, m):
	if n == 2 and m == 2:
		return 2
	elif n % 3 == 0:
		return m * (n // 3)
	elif m % 3 == 0:
		return n * (m // 3)
	elif n == 2 and m == 1:
		return 1
	elif n == 1 and m == 2:
		return 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n % 3 == 1 and m % 3 == 1:
		ans = 0
		if n > m:
			ans += m // 3 * 2
			ans += less(2, m % 3)
			n -= 2
			ans += n // 3 * m
			n = n % 3
			ans += m // 3 * n
			m = m % 3
			ans += less(n, m)
			print(ans)
		else:
			ans += n // 3 * 2
			ans += less(n % 3, 2)
			m -= 2
			ans += n // 3 * m
			n = n % 3
			ans += m // 3 * n
			m = m % 3
			ans += less(n, m)
			print(ans)
	else:
		ans = 0
		ans += n // 3 * m
		n = n % 3
		ans += m // 3 * n
		m = m % 3
		ans += less(n, m)
		print(ans)


answer = ''

def f(a, b):
	if a == 0 or b == 0:
		return 0
	if a == 1 and b == 3 or (a == 3 and b == 1) or (a == 1 and b == 1):
		return 1
	if a == 1 and b == 2 or (a == 2 and b == 1):
		return 1
	if a * b == 4:
		return 2
	return b // 3 * a + f(b % 3, a)
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b), max(a, b))
	answer += str(f(a, b)) + '\n'
print(answer)


t = int(input())
unp = []
for i in range(t):
	unp.append(list(map(int, input().split())))
for i in range(t):
	(n, m) = (unp[i][0], unp[i][1])
	if n == 1 and m == 1:
		print(0)
	else:
		s = 0
		if n > 2 or m > 2:
			n1 = n // 3 * m
			n2 = m // 3 * n
			if n1 < n2:
				n %= 3
				s += n1
				s += m // 3 * n
				m %= 3
			else:
				m %= 3
				s += n2
				s += n // 3 * m
				n %= 3
		if n == 1 and m == 1:
			s += 1
		elif n + m == 3:
			s += 1
		elif n + m == 4:
			s += 2
	print(s)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	z = n // 3 * k + k // 3 * (n % 3)
	if n % 3 + k % 3 == 4:
		z = z + 2
	elif n % 3 * (k % 3) != 0:
		z = z + 1
	print(z)


n = int(input())
for i in range(n):
	x = input().split()
	a = int(x[0])
	b = int(x[1])
	c = a * b
	if c % 3 == 0:
		print(c // 3)
	else:
		print(c // 3 + 1)


from math import *

def solve():
	(n, m) = map(int, input().split())
	print(ceil(n * m / 3))
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for v in range(t):
	(n, m) = map(int, input().split())
	pl = 0
	if n == 1 and m == 1:
		pl = 1
	if pl == 1:
		print(0)
	elif pl == 0:
		ans = 0
		if n > 2 or m > 2:
			n1 = n // 3 * m
			n2 = m // 3 * n
			if n2 >= n1:
				(n, m) = (m, n)
				(n1, n2) = (n2, n1)
			n %= 3
			ans += n1
			ans += m // 3 * n
			m %= 3
		if n == 1 and m == 1:
			ans += 1
		elif n + m == 3:
			ans += 1
		elif n + m == 4:
			ans += 2
	print(ans)


a = int(input())
A = []
for i in range(a):
	(n, m) = map(int, input().split())
	if n * m % 3 == 0:
		f = int(n * m / 3)
		A.append(str(f))
		continue
	else:
		f = m * n // 3
		b = m * n % 3
		if b == 1:
			f = f - 1
			b += 3
			b = int(b / 2)
			f += b
			A.append(str(f))
			continue
		else:
			b = int(b / 2)
			f += b
			A.append(str(f))
			continue
print('\n'.join(A))


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	if a % 3 == 1:
		m1 = a // 3 * b + b // 3 + (b % 3 > 0)
	elif a % 3 == 2:
		m1 = a // 3 * b + 2 * (b // 3 + (b % 3 > 0))
	else:
		m1 = (a // 3 + (a % 3 > 0)) * b
	if b % 3 == 1:
		m2 = b // 3 * a + a // 3 + (a % 3 > 0)
	elif b % 3 == 2:
		m2 = b // 3 * a + 2 * (a // 3 + (a % 3 > 0))
	else:
		m2 = (b // 3 + (b % 3 > 0)) * a
	print(min(m1, m2))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = m // 3 * n
	x = m % 3
	ans += n // 3 * x
	y = n % 3
	print(ans + min(x, y))


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve(n, m):
	res = 0
	prod = n * m
	mod3 = prod % 3
	if mod3 == 0:
		res = prod / 3
	elif mod3 > 1:
		res = int(prod / 3) + mod3 / 2
	elif mod3 == 1:
		res = int(prod / 3) + (mod3 + 3) / 2 - 1
	return int(res)
res = []
iter = inp()
i = 0
while i < iter:
	case = inlt()
	test = solve(case[0], case[1])
	res.append(test)
	i += 1
for r in res:
	print(r)


q = int(input())
for w in range(q):
	(m, n) = map(int, input().split())
	k1 = m // 3 * n
	if m % 3 != 0:
		k1 += n // 3 * (m % 3)
		if n % 3 != 0:
			k1 += m % 3
	k2 = n // 3 * m
	if n % 3 != 0:
		k2 += m // 3 * (n % 3)
		if m % 3 != 0:
			k2 += n % 3
	print(min(k1, k2))


def solve():
	(n, m) = list(map(int, input().split()))
	matrix = n * m
	print(matrix // 3 + min(1, matrix % 3))
for _ in range(int(input())):
	solve()


t = int(input())
ans = []
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	if n % 3 == 0 or m % 3 == 0:
		ans.append(m * n // 3)
	elif n == 1:
		ans.append(m // 3 + 1)
	elif m == 1:
		ans.append(n // 3 + 1)
	else:
		res1 = n // 3 * m + n % 3 * (m // 3 + 1)
		res2 = m // 3 * n + m % 3 * (n // 3 + 1)
		ans.append(min(res1, res2))
for f in ans:
	print(f)


t = int(input())
res = []
for _ in range(t):
	(n, m) = sorted(map(int, input().split()))
	if n % 3 == 0:
		res.append(m * n // 3)
	elif m % 3 == 0:
		res.append(m * (n // 3) + m // 3 * (n % 3))
	elif m % 3 == 1:
		if n % 3 == 2:
			res.append(m * (n // 3) + (m // 3 + 1) * (n % 3) - 1)
		else:
			res.append(m * (n // 3) + (m // 3 + 1) * (n % 3))
	else:
		res.append(m * (n // 3) + (m // 3 + 1) * (n % 3))
for i in res:
	print(i)


tst = int(input())
for i in range(tst):
	(x, y) = map(int, input().split())
	ans = x * y // 3
	print(ans + 1 if x * y % 3 != 0 else ans)


def colouring_rectangles():
	t = int(input())
	for i in range(t):
		(A, B) = input().split()
		a = int(A)
		b = int(B)
		if a * b % 3 == 0:
			print(a * b // 3)
		else:
			print(a * b // 3 + 1)
colouring_rectangles()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = n // 3 * m + m // 3 * (n % 3)
	if n % 3 == 1 and m % 3 == 1:
		k += 1
	else:
		k += n % 3 * (m % 3) // 2
	print(k)


num = int(input())
for i in range(num):
	(a, b) = map(int, input().split())
	remainder = a * b % 3
	quotient = a * b // 3
	if remainder == 0:
		print(quotient)
	else:
		print(quotient + 1)


cases = int(input())
for i in range(cases):
	R = list(map(int, input().split()))
	m = R[0]
	n = R[1]
	rem = m * n % 3
	if rem == 0:
		print(m * n // 3)
	else:
		print(m * n // 3 + 1)


from math import ceil
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	print(ceil(n * m / 3))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if min(n, m) == 1 and max(n, m) <= 3:
		print(1)
	elif min(n, m) == 1 and max(n, m) > 3:
		if max(n, m) % 3 == 0:
			print(max(n, m) // 3)
		else:
			print(max(n, m) // 3 + 1)
	elif n == 2 and m == 2:
		print(2)
	elif n * m % 3 == 0:
		print(n * m // 3)
	else:
		print(n * m // 3 + 1)


from math import *
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	print(ceil(a * b / 3))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if m * n % 3 == 0:
		print(m * n // 3)
	else:
		print(m * n // 3 + 1)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	print(n * m // 3 + (n * m % 3 != 0))


n = int(input())
num_list = []
for i in range(n):
	(a, b) = input().split(' ')
	(a, b) = (int(a), int(b))
	num_list.append([a, b])
for (x, y) in num_list:
	(tmp_min, tmp_max) = (x, y) if x < y else (y, x)
	k = tmp_max % 3
	m = tmp_min % 3
	if k == 0:
		print(tmp_max // 3 * tmp_min)
	elif k == 1:
		if m == 0:
			print(tmp_max // 3 * tmp_min + tmp_min // 3)
		else:
			print(tmp_max // 3 * tmp_min + tmp_min // 3 + 1)
	else:
		print(tmp_max // 3 * tmp_min + k * (tmp_min // 3) + m)


t = int(input())
for t1 in range(t):
	(n, m) = (int(x) for x in input().split())
	print((n * m + 2) // 3)


import math

def solve(n, m):
	return math.ceil(n * m / 3)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	ans = solve(n, m)
	print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(b * (a // 3) + a % 3 * (b // 3) + min(a % 3, b % 3))


loop = int(input())
for i in range(loop):
	inp = list(map(int, input().split()))
	print((inp[0] * inp[1] + 2) // 3)


import math as m
for _ in range(int(input())):
	print(m.ceil(m.prod(map(int, input().split())) / 3))


def coloringRectangles(n, m):
	a = n * m
	if a == 1:
		return 0
	elif a == 2:
		return 1
	else:
		p = a // 3
		q = a % 3
		if q == 2:
			q = 1
	return p + q
t = int(input())
final = []
for _ in range(t):
	(n, m) = map(int, input().split())
	final.append(coloringRectangles(n, m))
for _ in range(t):
	print(final[_])


def solver():
	(m, n) = input().split()
	m = int(m)
	n = int(n)
	if max(n, m) < 3:
		print(int(m * n / 2))
	elif n % 3 == 0 or m % 3 == 0:
		print(int(m * n / 3))
	elif n % 3 == m % 3:
		print(int((m * n + 2) / 3))
	else:
		print(int((m * n + 1) / 3))
test = int(input())
for i in range(test):
	solver()


import sys
import math
from bisect import bisect_right as br
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for i in range(int(input())):
	(r, c) = int_arr()
	a = 0
	b = 0
	div_r = r // 3
	a += div_r * c
	if r % 3 != 0:
		a += c // 3 * (r % 3)
		if c % 3 != 0:
			a += 1 * (r % 3)
	div_c = c // 3
	b += div_c * r
	if c % 3 != 0:
		b += r // 3 * (c % 3)
		if r % 3 != 0:
			b += 1 * (c % 3)
	print(min(a, b))


t = int(input())
for tc in range(t):
	(n, m) = list(map(int, input().strip().split()))
	if n * m % 3 == 0:
		print(int(n * m / 3))
	else:
		temp = int(n * m / 3)
		print(temp + 1)


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	print(math.ceil(n * m / 3))


def main():
	t = int(input())
	n = [0 for _ in range(t)]
	m = [0 for _ in range(t)]
	for i in range(t):
		(n[i], m[i]) = map(int, input().split())
	ans = [0 for _ in range(t)]
	for i in range(t):
		while True:
			if n[i] < m[i]:
				(n[i], m[i]) = (m[i], n[i])
			if m[i] == 0:
				break
			elif m[i] == 1:
				ans[i] += (n[i] + 2) // 3
				break
			elif m[i] == 2 and n[i] == 2:
				ans[i] += 2
				break
			elif m[i] == 2:
				ans[i] += n[i] // 3 * 2
				n[i] %= 3
			else:
				ans[i] += m[i] // 3 * n[i]
				m[i] %= 3
	for x in ans:
		print(x)
main()


for k in range(int(input())):
	(n, m) = input().split()
	Sum = int(n) * int(m)
	print((Sum + 2) // 3)


n = int(input())
for _ in range(n):
	(u, v) = map(int, input().split())
	e = u * v
	c = e // 3
	if e % 3 != 0:
		print(c + 1)
	else:
		print(c)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = 0
	a.sort()
	if a[0] * a[1] / 3 > a[0] * a[1] // 3:
		k = a[0] * a[1] // 3 + 1
	else:
		k = a[0] * a[1] // 3
	print(k)


x = int(input())
for i in range(x):
	(y, z) = map(int, input().split())
	if max([y, z]) > 2:
		if y * z % 3 == 0:
			print(y * z // 3)
		else:
			print(y * z // 3 + 1)
	else:
		print(y * z // 2)


t = int(input())
arr = []
c = 0
s = 0
for i in range(t):
	arr.append(input().split())
	arr[i][0] = int(arr[i][0])
	arr[i][1] = int(arr[i][1])
for i in range(t):
	s = arr[i][0] * arr[i][1]
	if s % 3 == 0:
		c = s // 3
	if (s % 3 == 1) | (s % 3 == 2):
		c = s // 3 + 1
	print(c)


def c_r(n, m):
	if n * m % 3 == 0:
		print(int(n * m / 3))
	else:
		print(int(n * m / 3 + 1))
in_t_case = int(input())
for i in range(in_t_case):
	(n, m) = map(int, input().split())
	c_r(n, m)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = a * b / 3
	d = math.ceil(c)
	print(d)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	print((n * m + 2) // 3)


from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
for _ in range(int(input())):
	(n, m) = map(int, input().split())

	def func(x, y):
		if x == 1:
			if y % 3 == 0:
				return y // 3
			else:
				return y // 3 + 1
		if y == 1:
			if x % 3 == 0:
				return x // 3
			else:
				return x // 3 + 1
		if x < 3 and y < 3:
			a = x * y
			if a == 2:
				return 1
			if a == 3:
				return 1
			if a == 4:
				return 2
			return 0
		if x >= 3:
			return y * (x // 3) + func(y, x % 3)
		else:
			return func(y, x)
	print(func(n, m))


import math
for t in range(int(input())):
	(r, c) = map(int, input().split())
	print(math.ceil(r * c / 3))


def colouringRectengle(n, m):
	x = n * m
	if x == 1 or x == 2 or x == 3:
		return 1
	if x == 4:
		return 2
	return (x + 2) // 3
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	print(colouringRectengle(n, m))


class Solution:

	def rectangles(self, x: int, y: int) -> int:
		area = x * y
		if area % 3 == 0:
			return area // 3
		elif area % 3 == 1:
			new = area // 3 - 1
			return 2 + new
		else:
			return 1 + area // 3
obj = Solution()
t = int(input())
for _ in range(t):
	(x, y) = list(map(int, input().split()))
	print(obj.rectangles(x, y))


_ = int(input())
for __ in range(_):
	(a, b) = map(int, input().split())
	p = a * b
	if p == 1:
		print(0)
		continue
	if p == 2:
		print(1)
		continue
	if p == 4:
		print(2)
		continue
	if p % 3 == 0:
		print(p // 3)
	elif (p - 2) % 3 == 0:
		print(1 + (p - 2) // 3)
	else:
		print(2 + (p - 4) // 3)


from math import ceil
k = int(input())
for i in range(k):
	(n, m) = (int(x) for x in input().split())
	print(ceil(n * m / 3))


from math import ceil
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	print(ceil(r * c / 3))


for _ in range(int(input())):
	(n, m) = map(int, input().split())

	def a(n, m):
		ans = n * (m // 3)
		if m % 3 == 2:
			return ans + min(n, 2 * (n // 3) + n % 3)
		elif m % 3 == 0:
			return ans
		return ans + (n % 3 != 0) + n // 3
	print(min(a(n, m), a(m, n)))


t = int(input())
for i in range(t):
	(r, c) = map(int, input().split())
	if r * c % 3 == 0:
		print(r * c // 3)
	else:
		print(r * c // 3 + 1)


from collections import Counter
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def f(longer_side):
	(ss_multiple, ss_remain) = (longer_side // 3, longer_side % 3)
	if ss_remain != 0:
		ss_multiple += 1
	return ss_multiple

def solve():
	(r, c) = [int(char) for char in input().split()]
	if r == 1:
		return f(c)
	elif c == 1:
		return f(r)
	(long_side, short_side) = (max(r, c), min(r, c))
	(ls_multiple, ls_remain) = (long_side // 3, long_side % 3)
	ans = ls_multiple * short_side
	if ls_remain == 0:
		return ans
	elif ls_remain == 1:
		return ans + f(short_side)
	elif short_side <= 3:
		return ans + min(short_side, ls_remain)
	else:
		ss_remain = short_side % 3
		ans += short_side // 3 * 2
		ans += min(ss_remain, ls_remain)
		return ans
for _ in range(int(input())):
	print(solve())


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = n * m // 3
	res += 1 if n * m % 3 != 0 else 0
	print(res)


for z in range(int(input())):
	(n, m) = map(int, input().strip().split())
	k = n * m
	if k % 3 == 0:
		print(k // 3)
		continue
	print(k // 3 + 1)


for i in range(int(input())):
	(n, m) = [int(a) for a in input().split()]
	b = 0
	if n % 3 == 0 or m % 3 == 0:
		b = m * n / 3
	else:
		b = m * n // 3 + 1
	print(int(b))