Michael is accused of violating the social distancing rules and creating a risk of spreading coronavirus. He is now sent to prison. Luckily, Michael knows exactly what the prison looks like from the inside, especially since it's very simple.

The prison can be represented as a rectangle $a\times b$ which is divided into $ab$ cells, each representing a prison cell, common sides being the walls between cells, and sides on the perimeter being the walls leading to freedom. Before sentencing, Michael can ask his friends among the prison employees to make (very well hidden) holes in some of the walls (including walls between cells and the outermost walls). Michael wants to be able to get out of the prison after this, no matter which cell he is placed in. However, he also wants to break as few walls as possible.

Your task is to find out the smallest number of walls to be broken so that there is a path to the outside from every cell after this.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 100$) — the number of test cases.

Each of the following $t$ lines contains two integers $a$ and $b$ ($1\leq a, b\leq 100$), representing a corresponding test case.


-----Output-----

For each test case print the single integer on a separate line — the answer to the problem.


-----Examples-----

Input
2
2 2
1 3
Output
4
3


-----Note-----

Some possible escape plans for the example test cases are shown below. Broken walls are shown in gray, not broken walls are shown in black.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
def func():
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().strip().split())
		print(a * b)
func()


t = int(input())
for o in range(t):
	n = [int(x) for x in input().split()]
	print(n[0] * n[1])


exec(int(input()) * 'n,m=map(int,input().split());print(n*m);')


n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	print(a * b)


t = int(input())
while t > 0:
	ans = 0
	(a, b) = map(int, input().split())
	ans = a * b
	print(ans)
	t -= 1


prim = int(input())
while prim > 0:
	lista = input().split(' ')
	a = int(lista[0])
	b = int(lista[1])
	c = a * b
	print(c)
	prim -= 1


for test in range(int(input())):
	(x, y) = map(int, input().split())
	print(x * y)


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	print(a * b)


for T in range(int(input())):
	(a, b) = map(int, input().split())
	print(a * b)


def solve():
	(a, b) = [int(n) for n in input().split(' ')]
	print(a * b)
for t in range(int(input())):
	solve()


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


import sys
input = sys.stdin.readline

class Problem:

	def __init__(self):
		pass

	def solve(self):
		t = int(input())
		for _ in range(t):
			(a, b) = map(int, input().split())
			ans = a * b
			print(ans)

def main():
	p = Problem()
	p.solve()
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	print(m * n)


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(a * b)


def answer(a, b):
	return a * b

def main():
	t = int(input())
	a = [0] * t
	b = [0] * t
	for j in range(t):
		(a[j], b[j]) = [int(i) for i in input().split()]
	for j in range(t):
		print(answer(a[j], b[j]))
main()


try:
	n = int(input())
	for i in range(n):
		m = list(map(int, input().split()))
		a = m[0]
		b = m[1]
		print(a * b)
except:
	pass


t = int(input())
for i in range(t):
	(a, b) = tuple(map(int, input().split()))
	print(a * b)


t = int(input())
for _ in range(0, t):
	(a, b) = map(int, input().split())
	print(a * b)


for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	print(a * b)


t = int(input())
for i in range(t):
	l = input()
	l = l.split()
	a = int(l[0])
	b = int(l[1])
	print(a * b)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	ans = a * b
	print(ans)


import sys

def read_a_num(line):
	[n] = list(map(int, line.strip().split(' ')))
	return n

def read_two_num(line):
	[n1, n2] = list(map(int, line.strip().split(' ')))
	return (n1, n2)
lines = sys.stdin.readlines()
t = read_a_num(lines[0])
for line in lines[1:t + 1]:
	(a, b) = read_two_num(line)
	print(a * b)


for _ in range(int(input())):
	(m, n) = [int(i) for i in input().split()]
	print(m * n)


def solution(a, b):
	return a * b

def main():
	t = int(input())
	output = []
	for i in range(t):
		(a, b) = list(map(int, input().split()))
		output.append(solution(a, b))
	for i in range(t):
		print(output[i])
main()


try:
	import sys

	def solve():
		(a, b) = map(int, input().split())
		sys.stdout.write(str(a * b) + '\n')
	test = int(input())
	while test != 0:
		solve()
		test -= 1
except EOFError:
	print(' ')


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	print(n * m)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	print(a * b)


for x in range(int(input())):
	(a, b) = map(int, input().split())
	print(a * b)


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


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


t = input()
m = int(t)
while m > 0:
	a = input()
	b = a.split()
	print(int(b[0]) * int(b[1]))
	m = m - 1


n = int(input())
for i in range(n):
	(A, B) = input().split()
	print(int(A) * int(B))


def Prison_break():
	a = int(input())
	for i in range(a):
		n = list(map(int, input().split()))
		print(n[0] * n[1])
Prison_break()


t = int(input())
for test in range(1, t + 1):
	(n, k) = map(int, input().split())
	print(n * k)


import math
import sys
input = sys.stdin.readline
t = int(input())
for i1 in range(t):
	(a, b) = map(int, input().split())
	k = b * a
	print(k)


cases = int(input())

def solve():
	(a, b) = list(map(int, input().strip().split()))
	print(a * b)
for case in range(cases):
	solve()


import math

def getint():
	return [int(i) for i in input().split()]

def getstr():
	return [str(i) for i in input().split()]

def solve():
	(a, b) = getint()
	print(a * b)
for _ in range(int(input())):
	solve()


for _ in ' ' * int(input()):
	(a, b) = map(int, input().split())
	print(a * b)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	print(x * y)


a = int(input())
for i in range(a):
	(b, c) = list(map(int, input().split()))
	print(b * c)


T = int(input())
for i in range(T):
	ls = list(map(int, input().split()))
	print(ls[0] * ls[1])


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		print(n * k)
except:
	pass


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	print(n * m)


for _ in range(int(input())):
	(i, j) = map(int, input().split())
	print(i * j)


from functools import reduce

def escape():
	test = int(input())
	t = []
	for i in range(0, test):
		x = list(map(int, input().split()))
		t.append(x)
	for i in t:
		print(reduce(lambda a, b: a * b, i))
escape()


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(x * y)


for s in [*open(0)][1:]:
	(a, b) = map(int, s.split())
	print(a * b)


t = int(input())
for _ in range(t):
	(a, b) = (int(el) for el in input().split())
	print(a * b)


t = int(input())
ans = []
for i in range(t):
	(a, b) = map(int, input().split())
	ans.append(a * b)
for item in ans:
	print(str(item))


n = int(input())
l = []
for i in range(n):
	(x, y) = map(int, input().strip().split())
	l.append(x * y)
for i in l:
	print(i)


t = int(input())
while t:
	t -= 1
	(a, b) = map(int, input().split())
	print(a * b)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(n * k)


from math import *
n = int(input())
for i in range(0, n):
	(a, b) = map(int, input().split())
	print(a * b)


for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	print(a * b)


import math
import sys
import collections
import bisect
import time

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

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

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	(n, m) = get_ints()
	print(n * m)


T = int(input())
for i in range(T):
	(A, B) = input().split()
	A = int(A)
	B = int(B)
	print(A * B)


import math

def solve():
	(a, b) = list(map(int, input().split()))
	return a * b
tc = int(input())
for _ in range(tc):
	print(solve())


inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))

def solve():
	(a, b) = inm()
	print(a * b)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
main()


N = int(input())
for i in range(N):
	(a, b) = map(int, input().split())
	print(a * b)