Mr. Chef is the manager of the Code cinemas and after a long break, the theatres are now open to the public again. To compensate for the loss in revenue due to Covid-19, Mr. Chef wants to maximize the profits for every show from now on and at the same time follow the guidelines set the by government.
The guidelines are:

If two people are seated in the same row, there must be at least one empty seat between them.
If two people are seated in different rows, there must be at least one completely empty row between them. That is, if there are people seated in rows i and j where i < j, there must be some row k such that i < k < j and nobody is seated in row k.

Given the information about the number of rows and the number of seats in each row, find the maximum number of tickets Mr. Chef can sell. 

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input containing two space-separated integers N, M — the number of rows and the number of seats in each row, respectively.

------ Output Format ------ 

For each test case, output a single line containing one integer – the maximum number of tickets Mr. Chef can sell.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N,M≤ 100$

----- Sample Input 1 ------ 
3
1 5
3 3
4 4
----- Sample Output 1 ------ 
3
4
4
----- explanation 1 ------ 
Test Case 1: There is only one row with five seats. Mr. Chef can sell a maximum of 3 tickets for seat numbers 1, 3 and 5.

Test Case 2: There are three rows with three seats each. Mr. Chef can sell a maximum of 4 tickets, for seats at the start and end of row numbers 1 and 3.

Test Case 3: There are four rows with four seats each. Mr. Chef can sell a maximum of 4 tickets, for example by choosing the seats at the start and end of row numbers 1 and 4.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from math import ceil
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(ceil(m / 2) * ceil(n / 2))


test_cases = int(input())
while test_cases > 0:
	(num_rows, num_cols, count) = (0, 0, 0)
	(num_rows, num_cols) = map(int, input().split())
	for i in range(0, num_rows, 2):
		for j in range(0, num_cols, 2):
			count += 1
	print(count)
	test_cases -= 1


n = int(input())
for i in range(n):
	c = 0
	(a, b) = list(map(int, input().split()))
	for i in range(0, a, 2):
		for j in range(0, b, 2):
			c += 1
	print(c)


for t in range(int(input())):
	(a, b) = map(int, input().split())
	v = a // 2
	if a % 2 != 0:
		v = v + 1
	v1 = b // 2
	if b % 2 != 0:
		v1 = v1 + 1
	print(v1 * v)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = math.ceil(x / 2)
	c = math.ceil(y / 2)
	print(s * c)


for i in range(int(input())):
	x = [int(x) for x in input().split()]
	print((x[0] + 1) // 2 * ((x[1] + 1) // 2))


for _ in range(int(input())):
	(y, z) = map(int, input().split())
	seat = z / 2
	if seat == int(seat):
		seat = seat
	else:
		seat = int(seat) + 1
	if y == 1:
		print(int(seat))
	else:
		row = y / 2
		if row == int(row):
			row = y / 2
		else:
			row = int(y / 2) + 1
		print(int(row * seat))


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = 0
	for i in range(1, m + 1, 2):
		a += 1
	if n == 1:
		print(a)
	else:
		print(a * math.ceil(n / 2))


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


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


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


for i in range(int(input())):
	(num, res) = map(int, input().split())
	c = 0
	for j in range(1, num + 1):
		if j % 2 != 0:
			l = [i for i in range(1, res + 1) if i % 2 != 0]
			c += len(l)
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	acc = 0
	acc = (m // 2 + m % 2) * (n // 2 + n % 2)
	print(acc)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	acc = 0
	for i in range(0, n, 2):
		for j in range(0, m, 2):
			acc += 1
	print(acc)


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


t = int(input())
for i in range(t):
	(i, j) = map(int, input().split())
	rows = i // 2
	col = j // 2
	if i % 2 == 1:
		rows += 1
	if j % 2 == 1:
		col += 1
	print(rows * col)


for _ in range(int(input())):
	(rows, seats) = map(int, input().split())
	count = 0
	for i in range(0, rows, 2):
		for j in range(0, seats, 2):
			count = count + 1
	print(count)


n = int(input())
while n > 0:
	(t, w) = map(int, input().split())
	if t % 2 == 0:
		s = t // 2
	else:
		s = t // 2 + 1
	if w % 2 == 0:
		d = w // 2
	else:
		d = w // 2 + 1
	print(s * d)
	n = n - 1


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


c = int(input())
for i in range(c):
	(n, m) = map(int, input().split())
	if n % 2 == 1 or m % 2 == 1:
		n = n + 1
		m = m + 1
	a = int(n / 2)
	b = int(m / 2)
	print(int(a * b))


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


import math
t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	ans = 0
	if x % 2 == 0:
		ans = x // 2
	else:
		ans = x // 2 + 1
	if y % 2 == 0:
		ans *= y // 2
	else:
		ans *= y // 2 + 1
	print(ans)
	t -= 1


t = int(input())
for nt in range(t):
	(n, m) = map(int, input().split())
	count = 0
	for i in range(n):
		if i % 2 != 0:
			continue
		if m % 2 == 0:
			count += m // 2
		else:
			count += m // 2 + 1
	print(count)


t = int(input())
for i in range(t):
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	q = int()
	p = int()
	if m % 2 == 0:
		q = m / 2
	else:
		q = (m - 1) / 2 + 1
	if n % 2 == 0:
		p = n / 2
	else:
		p = (n - 1) / 2 + 1
	print(int(p * q))


for i in range(int(input())):
	x = list(map(int, input().split()))
	n = 0
	for i in range(1, x[0] + 1):
		if i % 2 != 0:
			n = n + 1
	b = 0
	for i in range(1, x[1] + 1):
		if i % 2 != 0:
			b = b + 1
	b = b * n
	print(b)


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	if a % 2 != 0:
		a += 1
	if b % 2 != 0:
		b += 1
	a1 = a // 2
	b1 = b // 2
	print(a1 * b1)


T = int(input())
for _ in range(0, T):
	(n, m) = map(int, input().split(' '))
	if n == 1:
		if m % 2 == 0:
			print(m // 2)
		else:
			print(m // 2 + 1)
		continue
	if n % 2 == 1:
		n = n + 1
	if m % 2 == 1:
		m = m + 1
	if n % 2 == 0:
		n = n / 2
		ans = n * (m // 2)
		print(int(ans))


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


import math
t = int(input())
for i in range(t):
	x = input().split()
	(row, column) = (int(x[0]), int(x[1]))
	(row, column) = (math.ceil(row / 2), math.ceil(column / 2))
	print(str(row * column))


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


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


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


for _ in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	c = 0
	for i in range(0, x, 2):
		for j in range(0, y, 2):
			c += 1
	print(c)


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


T = int(input())
for t in range(0, T):
	(N_rows, M_seats_per_row) = map(int, input().split())
	eff_rows = N_rows // 2 + N_rows % 2
	eff_seats_per_row = M_seats_per_row // 2 + M_seats_per_row % 2
	max_seats = eff_rows * eff_seats_per_row
	print(max_seats)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	if N % 2 == 0:
		if M % 2 == 0:
			print(N // 2 * (M // 2))
		else:
			print(N // 2 * (M // 2 + 1))
	elif M % 2 == 0:
		print((N // 2 + 1) * (M // 2))
	else:
		print((N // 2 + 1) * (M // 2 + 1))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	k = 0
	for j in range(1, n + 1):
		if j % 2 != 0:
			l = [i for i in range(1, m + 1) if i % 2 != 0]
			k += len(l)
	print(k)


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


for i in range(int(input())):
	(n, m) = map(int, input().split())
	count = 0
	for j in range(0, n, 2):
		for k in range(0, m, 2):
			count = count + 1
	print(count)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(n):
		for j in range(m):
			if i % 2 == 0 and j % 2 == 0:
				ans += 1
	print(ans)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	print((N // 2 + (0 if N % 2 == 0 else 1)) * (M // 2 + (0 if M % 2 == 0 else 1)))


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


for i in range(int(input())):
	b = list(map(int, input().split()))
	count = 0
	for i in range(1, b[0] + 1, 2):
		for j in range(1, b[1] + 1, 2):
			count += 1
	print(count)


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


for i in range(int(input())):
	(N, M) = map(int, input().split())
	if N % 2 == 0:
		r = N // 2
	else:
		r = N // 2 + 1
	if M % 2 == 0:
		s = M // 2
	else:
		s = M // 2 + 1
	print(r * s)


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


tc = int(input())
for _ in range(tc):
	(a, b) = map(int, input().split())
	if b % 2 != 0:
		b += 1
	if a % 2 != 0:
		a += 1
	oneRow = b // 2
	noCol = a // 2
	print(oneRow * noCol)


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


for i in range(int(input())):
	(rows, seats) = map(int, input().split())
	if seats % 2 == 0:
		res = seats / 2
	else:
		res = (seats + 1) / 2
	if rows % 2 == 0:
		res1 = rows / 2
	else:
		res1 = (rows + 1) / 2
	print(int(res * res1))


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


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


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


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = 0
	b = 0
	if n % 2 != 0 and m % 2 != 0:
		a = n // 2 + 1
		b = m // 2 + 1
	elif n % 2 == 0 and m % 2 != 0:
		a = n // 2
		b = m // 2 + 1
	elif n % 2 != 0 and m % 2 == 0:
		a = n // 2 + 1
		b = m // 2
	else:
		a = n // 2
		b = m // 2
	print(a * b)


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	c = 0
	for i in range(0, n, 2):
		for j in range(0, m, 2):
			c += 1
	print(c)


q = int(input())
while q > 0:
	(n, m) = map(int, input().split())
	if n % 2 == 0:
		x = n // 2
	else:
		x = (n + 1) // 2
	if m % 2 == 0:
		y = m // 2
	else:
		y = (m + 1) // 2
	print(x * y)
	q = q - 1


i = int(input())
x = 0
list1 = []
while x < i:
	ooo = input().split()
	rows = int(ooo[0]) / 2
	coloumns = int(ooo[1]) / 2
	if int(ooo[0]) % 2 == 1:
		rows = int(ooo[0]) // 2 + 1
	if int(ooo[1]) % 2 == 1:
		coloumns = int(ooo[1]) // 2 + 1
	list1.append(int(rows * coloumns))
	x = x + 1
for ele in list1:
	print(ele)


T = int(input())
while T > 0:
	(N, M) = map(int, input().split())
	if N % 2 == 0:
		row = N // 2
	else:
		row = N // 2 + 1
	if M % 2 == 0:
		col = M // 2
	else:
		col = M // 2 + 1
	print(row * col)
	T -= 1


for i in range(int(input())):
	(x, y) = map(int, input().split())
	c1 = c2 = 0
	if x % 2 != 0:
		c1 = (x + 1) // 2
	else:
		c1 = x // 2
	if y % 2 != 0:
		c2 = (y + 1) // 2
	else:
		c2 = y // 2
	total = c1 * c2
	print(total)