You are playing a game on a $n \times m$ grid, in which the computer has selected some cell $(x, y)$ of the grid, and you have to determine which one.

To do so, you will choose some $k$ and some $k$ cells $(x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)$, and give them to the computer. In response, you will get $k$ numbers $b_1,\, b_2, \ldots b_k$, where $b_i$ is the manhattan distance from $(x_i, y_i)$ to the hidden cell $(x, y)$ (so you know which distance corresponds to which of $k$ input cells).

After receiving these $b_1,\, b_2, \ldots, b_k$, you have to be able to determine the hidden cell. What is the smallest $k$ for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses?

As a reminder, the manhattan distance between cells $(a_1, b_1)$ and $(a_2, b_2)$ is equal to $|a_1-a_2|+|b_1-b_2|$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The single line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^9$) — the number of rows and the number of columns in the grid.


-----Output-----

For each test case print a single integer — the minimum $k$ for that test case.


-----Examples-----

Input
2
2 3
3 1
Output
2
1


-----Note-----

In the first test case, the smallest such $k$ is $2$, for which you can choose, for example, cells $(1, 1)$ and $(2, 1)$.

Note that you can't choose cells $(1, 1)$ and $(2, 3)$ for $k = 2$, as both cells $(1, 2)$ and $(2, 1)$ would give $b_1 = 1, b_2 = 2$, so we wouldn't be able to determine which cell is hidden if computer selects one of those.

In the second test case, you should choose $k = 1$, for it you can choose cell $(3, 1)$ or $(1, 1)$.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for s in [*open(0)][1:]:
	print(2 - s.split().count('1'))


for s in [*open(0)][1:]:
	print(2 - (s == '1 1\n') - ('1' in s.split()))


def main():

	def solve(n, m):
		if n == m == 1:
			return 0
		if n == 1 or m == 1:
			return 1
		return 2
	t = int(input())
	ans = []
	for _ in range(t):
		(n, m) = [int(x) for x in input().split()]
		ans.append(solve(n, m))
	print('\n'.join(map(str, ans)))
import sys, threading
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


import sys
for _ in range(int(sys.stdin.readline())):
	(n, m) = map(int, sys.stdin.readline().split())
	if n == m == 1:
		print(0)
	elif min(n, m) == 1:
		print(1)
	else:
		print(2)


for _ in [*open(0)][1:]:
	(a, b) = map(int, _.split())
	print('012'[(a > 1 or b > 1) + (a > 1 and b > 1)])


n = int(input())
lis = [0 for _ in range(n)]
for i in range(n):
	lis[i] = list(map(int, input().split()))
for i in range(n):
	n = lis[i][0]
	m = lis[i][1]
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b == 1:
		print(0)
	elif a == 1 or b == 1:
		print(1)
	else:
		print(2)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
		continue
	if n == 1 or m == 1:
		print(1)
		continue
	print(2)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	l = L()
	if max(l) == 1:
		print(0)
	elif 1 in l:
		print(1)
	else:
		print(2)


import sys
import math
from fractions import Fraction
from decimal import *
input = sys.stdin.readline
t = int(input())
while t > 0:
	inp = input().strip()
	s = [int(x) for x in inp.split(' ')]
	n = s[0]
	m = s[1]
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)
	t -= 1


from collections import Counter
from math import ceil, floor, log
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	(n, m) = inp_multi()
	if n == 1 and m == 1:
		print(0)
		continue
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


from itertools import product
import itertools
import math
import sys
import heapq
from collections import deque
MOD = 1000000000007

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1
ans = 0
K = int(sys.stdin.readline().strip())
x = 0
y = 0
for _ in range(K):
	(m, n) = list(map(int, sys.stdin.readline().strip().split()))
	if m == 1 and n == 1:
		print(0)
	elif m == 1 or n == 1:
		print(1)
	else:
		print(2)


t = int(input())
l = []
for i in range(t):
	(m, n) = [int(j) for j in input().split()]
	if m == 1 and n == 1:
		l.append(0)
	elif m == 1 or n == 1:
		l.append(1)
	else:
		l.append(2)
for i in l:
	print(i)


import sys
import math
input = sys.stdin.readline

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

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

def inltstr():
	return list(map(str, input().split()))

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

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

def factorial(n):
	if n == 1:
		return n
	elif n < 1:
		return 'NA'
	else:
		return n * factorial(n - 1)

def coeffBin(k):
	return factorial(k + 1) / (factorial(2) * factorial(k - 1))

def solve(n, m):
	count = 0
	if n == 1 and m == 1:
		return 0
	elif n == 1 or m == 1:
		return 1
	else:
		return 2
res = []
iter = inp()
i = 0
while i < iter:
	arr = inlt()
	result = solve(arr[0], arr[1])
	res.append(result)
	i += 1
for r in res:
	print(r)


sets_num = int(input())
answers = []
for i in range(sets_num):
	(a, b) = map(int, input().split())
	answers.append(int(a > 1) + int(b > 1))
for i in answers:
	print(i)


import sys

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_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		(n, m) = get_ints()
		if n == 1 and m == 1:
			get_print_int(0)
		else:
			get_print_int(min(n, m, 2))
solve()


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import time
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split()]
	return res

def read_list_of_ints_zero():
	return [int(val) - 1 for val in input().rstrip('\n').split()]

def read_str():
	return input().rstrip()

def main():
	tests = read_one_int()
	for _ in range(tests):
		(a, b) = read_list_of_ints()
		if a == b == 1:
			print(0)
			continue
		print(min(2, min(a, b)))
main()


n = int(input())
killer = []
for i in range(n):
	mylist = list(map(int, input().split()))
	if [1, 1] == mylist:
		killer.append(0)
	elif 1 in mylist and [1, 1] != mylist:
		killer.append(1)
	else:
		killer.append(2)
print(*killer, sep='\n')


k = int(input())
result = []
for i in range(k):
	coor = []
	coor = input().split()
	if coor[0] == coor[1] and coor[0] == '1':
		result.append(0)
	elif coor[0] == '1' or coor[1] == '1':
		result.append(1)
	else:
		result.append(2)
for j in result:
	print(j)


def main():
	n = int(input())
	lst = []
	for i in range(n):
		a = input().split()
		if int(a[0]) == 1 and int(a[1]) == 1:
			lst.append(0)
		elif int(a[0]) <= 1 or int(a[1]) <= 1:
			lst.append(1)
		else:
			lst.append(2)
	for i in range(n):
		print(lst[i])
main()


cases = int(input())
for _ in range(cases):
	(a, b) = map(int, input().split())
	if a == b == 1:
		print(0)
	elif min(a, b) == 1:
		print(1)
	else:
		print(2)


t = int(input())
out = []
for i in range(t):
	(n, m) = map(int, input().split())
	if n * m == 1:
		out.append(0)
	else:
		out.append(min(2, n, m))
for o in out:
	print(o)


for _ in range(int(input())):
	inp = input().split()
	a = inp.count('1')
	if a == 1:
		print(1)
	elif a == 2:
		print(0)
	else:
		print(2)


cases = int(input())
ans = []
while cases > 0:
	(n, m) = list(map(int, input().split()))
	cases -= 1
	if n == 1 and m == 1:
		ans.append(0)
	elif n == 1 or m == 1:
		ans.append(1)
	else:
		ans.append(2)
for i in ans:
	print(i)


trails = int(input())
answer_list = []
for x in range(trails):
	numbers = input().split(' ')
	answer = 2
	for s in numbers:
		if 1 == int(s):
			answer = 1
	if numbers == ['1', '1']:
		answer = 0
	answer_list.append(answer)
for g in answer_list:
	print(g)


a = int(input())
b = []
for i in range(a):
	b.append(list(input().split()))
for i in range(a):
	c = int(b[i][0])
	d = int(b[i][1])
	if c == 1 and d == 1:
		print(0)
	elif c == 1 or d == 1:
		print(1)
	else:
		print(2)


n = int(input())
killer = []
for i in range(n):
	(x, y) = map(int, input().split())
	if x == 1 and y == 1:
		killer.append(0)
	elif y == 1 or x == 1:
		killer.append(1)
	else:
		killer.append(2)
print(*killer, sep='\n')


for i in range(int(input())):
	(m1, n1) = input().split()
	if m1 == '1' and n1 == '1':
		print('0')
	elif m1 == '1' or n1 == '1':
		print('1')
	else:
		print('2')


inp1 = int(input())
for i in range(inp1):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if a == 1 and b == 1:
		print('0')
	elif a == 1 or b == 1:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	a = input().split()
	print(2 - a.count('1'))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b and a == 1:
		print(0)
	else:
		print(min(2, min(a, b)))


tc = int(input())
for i in range(tc):
	t = input().split()
	if t[0] == '1' and t[1] == '1':
		print('0')
	elif t[0] == '1' and t[1] != '1':
		print('1')
	elif t[1] == '1' and t[0] != '1':
		print('1')
	else:
		print('2')


for i in range(int(input())):
	count = 0
	x = input().split()
	for i in x:
		if i == '1':
			count += 1
	if count == 0:
		print(2)
	elif count == 1:
		print(1)
	elif count == 2:
		print(0)


x = int(input())
for i in range(x):
	m = input().split()
	m1 = int(m[0])
	m2 = int(m[1])
	if m1 == 1 and m2 == 1:
		print(0)
	elif m1 == 1 or m2 == 1:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	if n == 1 and m == 1:
		print(0)
	elif min(n, m) == 1:
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = 0 if n == 1 and m == 1 else min(n, m, 2)
	print(ans)


def fun(ls):
	(a, b) = ls
	if a == 1 and b == 1:
		print(0)
	elif a == 1 or b == 1:
		print(1)
	else:
		print(2)
T = int(input())
for i in range(T):
	ls = list(map(int, input().split()))
	fun(ls)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x == 1 and y == 1:
		print(0)
	else:
		print(min(x, y, 2))


for T in range(int(input())):
	(m, n) = input().split()
	if int(m) == 1 and int(n) == 1:
		print(0)
	elif int(m) == 1 or int(n) == 1:
		print(1)
	else:
		print(2)


import sys
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	(a, b) = ari()
	if a == 1 and b == 1:
		print(0)
	elif a == 1 or b == 1:
		print(1)
	else:
		print(2)
	return
for _ in range(test_case):
	ans()


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


import sys
from os import path
import math
import time
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
INT_MAX = 10 ** 9
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = int(input())
for _ in range(t):
	[n, m] = list(map(int, input().split()))
	if n == m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


cases = int(input())
for i in range(cases):
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print('0')
		continue
	if n == 1 or m == 1:
		print('1')
	else:
		print('2')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	print([2, [1, 0][n == m]][n == 1 or m == 1])


for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	if a == 1 and b == 1:
		print(0)
	elif a == 1 or b == 1:
		print(1)
	else:
		print(2)


tt = int(input())
for i in range(tt):
	(n, m) = map(int, input().split())
	if n == m == 1:
		print(0)
	else:
		print(min(n, m, 2))


t = int(input())
while t > 0:
	t -= 1
	inp = input()
	(n, m) = inp.split(' ')
	n = int(n)
	m = int(m)
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)


a = int(input())
for i in range(a):
	b = input()
	c = b.split()
	n = int(c[0])
	m = int(c[-1])
	if m == 1 and n == 1:
		print(0)
	elif m == 1 or n == 1:
		print(1)
	else:
		print(2)


def solve():
	(n, m) = map(int, input().split())
	if n > m:
		(n, m) = (m, n)
	if n == 1:
		if m == 1:
			print(0)
		else:
			print(1)
	else:
		print(2)
t = int(input())
for i in range(t):
	solve()


from collections import Counter, deque
import io, os, math
t = int(input())

def GO_LIFE():
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(0)
	elif n == 1 or m == 1:
		print(1)
	else:
		print(2)
while t > 0:
	GO_LIFE()
	t -= 1


def main():
	(n, m) = map(int, input().split())
	if n == m == 1:
		return 0
	if min(n, m) == 1:
		return 1
	else:
		return 2
tests = int(input())
while tests:
	tests -= 1
	print(main())


t = int(input())
for t1 in range(t):
	(n, m) = (int(x) for x in input().split())
	if n >= 2 and m >= 2:
		print(2)
	elif n == 1 and m == 1:
		print(0)
	else:
		print(1)


t = int(input())
while t != 0:
	t -= 1
	(n, m) = [int(i) for i in input().split()]
	if [n, m] == [1, 1]:
		print(0)
		continue
	if 1 in [n, m]:
		print(1)
		continue
	else:
		print(2)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if x == 1 and y == 1:
		print(0)
	elif x == 1:
		print(1)
	elif y == 1:
		print(1)
	else:
		print(2)


n = input()
for i in range(int(n)):
	A = input().split()
	if A[0] == '1' and A[1] == '1':
		print(0)
	elif A[0] == '1' or A[1] == '1':
		print(1)
	else:
		print(2)


m = int(input())
for i in range(m):
	(a1, b1) = map(int, input().split())
	if a1 == 1 and b1 == 1:
		print(0)
	elif a1 == 1 or b1 == 1:
		print(1)
	else:
		print(2)