There's a chip in the point $(0, 0)$ of the coordinate plane. In one operation, you can move the chip from some point $(x_1, y_1)$ to some point $(x_2, y_2)$ if the Euclidean distance between these two points is an integer (i.e. $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ is integer).

Your task is to determine the minimum number of operations required to move the chip from the point $(0, 0)$ to the point $(x, y)$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 3000$) — number of test cases.

The single line of each test case contains two integers $x$ and $y$ ($0 \le x, y \le 50$) — the coordinates of the destination point.


-----Output-----

For each test case, print one integer — the minimum number of operations required to move the chip from the point $(0, 0)$ to the point $(x, y)$.


-----Examples-----

Input
3
8 6
0 0
9 15
Output
1
0
2


-----Note-----

In the first example, one operation $(0, 0) \rightarrow (8, 6)$ is enough. $\sqrt{(0-8)^2+(0-6)^2}=\sqrt{64+36}=\sqrt{100}=10$ is an integer.

In the second example, the chip is already at the destination point.

In the third example, the chip can be moved as follows: $(0, 0) \rightarrow (5, 12) \rightarrow (9, 15)$. $\sqrt{(0-5)^2+(0-12)^2}=\sqrt{25+144}=\sqrt{169}=13$ and $\sqrt{(5-9)^2+(12-15)^2}=\sqrt{16+9}=\sqrt{25}=5$ are integers.

Difficulty: EASY
Tags: Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x == 0 and y == 0:
		print(0)
	elif x == 0 or y == 0:
		print(1)
	elif (x ** 2 + y ** 2) ** 0.5 % 1 == 0:
		print(1)
	else:
		print(2)


import sys
t = int(sys.stdin.readline())
for k in range(0, t):
	(x, y) = map(int, sys.stdin.readline().split())
	r = (x ** 2 + y ** 2) ** 0.5
	if r == 0:
		s = '0'
	elif r % 1 == 0:
		s = '1'
	else:
		s = '2'
	sys.stdout.write(s + '\n')


n_test_cases = int(input())
results = []
for _ in range(n_test_cases):
	(x, y) = tuple([int(x) for x in input().split()])
	if x == 0 and y == 0:
		results.append(0)
		continue
	a = (x * x + y * y) ** 0.5
	if a - int(a) == 0:
		results.append(1)
	else:
		results.append(2)
for result in results:
	print(result)


import sys
rl = sys.stdin.readline
T = int(rl())
for _ in range(T):
	(x, y) = map(int, rl().split())
	if x == 0 and y == 0:
		print(0)
	elif (x ** 2 + y ** 2) ** (1 / 2) == int((x ** 2 + y ** 2) ** (1 / 2)):
		print(1)
	else:
		print(2)


def solve():
	if n == 0 and m == 0:
		return 0
	if ((n ** 2 + m ** 2) ** 0.5).is_integer():
		return 1
	return 2
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(solve())


n = int(input())
res = ''
for x in range(n):
	(x, y) = map(int, input().split())
	c = 0
	(x1, y1) = (0, 0)
	s = (x ** 2 + y ** 2) ** (1 / 2)
	if s - int(s) == 0 and (x != 0 or y != 0):
		res += '1\n'
	elif x == 0 and y == 0:
		res += '0\n'
	else:
		res += '2\n'
print(res)


for s in [*open(0)][1:]:
	(x, y) = map(int, s.split())
	print((x | y > 0) + (int((d := ((x * x + y * y) ** 0.5))) < d))


import math
import sys
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())
t = inp()
for i in range(t):
	(x, y) = invr()
	temp = math.sqrt(y ** 2 + x ** 2)
	if int(temp) == 0:
		print(0)
		continue
	elif temp == int(temp):
		print(1)
		continue
	print(2)


import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
	a = int(input())
	for i in range(a):
		(x, y) = map(int, input().split())
		if x == 0 and y == 0:
			print(f'0\n')
		elif round((x ** 2 + y ** 2) ** 0.5) == (x ** 2 + y ** 2) ** 0.5:
			print(f'1\n')
		else:
			print(f'2\n')
main()


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	(x, y) = M()
	if x == 0 and y == 0:
		print(0)
		continue
	if (x * x + y * y) ** 0.5 == int((x * x + y * y) ** 0.5):
		print(1)
	else:
		print(2)


from math import sqrt
t = int(input())
while t > 0:
	t = t - 1
	[x, y] = input().split()
	x = int(x)
	y = int(y)
	if x == 0 and y == 0:
		print(0)
		continue
	if sqrt(x * x + y * y) == int(sqrt(x * x + y * y)):
		print(1)
	else:
		print(2)


import sys

def test():
	(x, y) = sys.stdin.readline().strip().split(' ')
	x = int(x)
	y = int(y)
	if x == 0 and y == 0:
		print(0)
	else:
		sq = x * x + y * y
		if int(sq ** 0.5 + 0.5) ** 2 == sq:
			print(1)
		else:
			print(2)
num_test = int(sys.stdin.readline())
for _ in range(num_test):
	test()


import math
import sys
input = sys.stdin.readline
for i in range(int(input())):
	(x, y) = tuple(map(int, input().split()))
	s = int(math.sqrt(x * x + y * y))
	if x == 0 and y == 0:
		print(0, end='\n')
	elif s * s == x * x + y * y:
		print(1, end='\n')
	else:
		print(2, end='\n')


import sys
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())
for _ in range(inp()):
	lst = inlt()
	tmp = (lst[0] ** 2 + lst[1] ** 2) ** 0.5
	if tmp == 0:
		print(0)
	elif tmp == int(tmp):
		print(1)
	else:
		print(2)


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


T = int(input())
while T:
	T -= 1
	(x, y) = map(int, input().split())

	def Euclidean(p1, p2):
		return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5
	init = (0, 0)
	goal = (x, y)
	if goal == init:
		print(0)
	elif Euclidean(init, goal).is_integer():
		print(1)
	else:
		print(2)


t = int(input())
a = []
for _ in range(t):
	a.append(list(map(int, input().split())))
for i in range(t):
	if a[i][0] == 0 and a[i][1] == 0:
		print(0)
	elif int((a[i][0] ** 2 + a[i][1] ** 2) ** 0.5) == (a[i][0] ** 2 + a[i][1] ** 2) ** 0.5:
		print(1)
	else:
		print(2)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = math.sqrt(a ** 2 + b ** 2)
	if a == 0 and b == 0:
		print(0)
	elif math.floor(x) == math.ceil(x):
		print(1)
	else:
		print(2)


import sys
from math import *

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

def get_string():
	return sys.stdin.readline().strip()
t = get_ints()[0]
for _ in range(t):
	(x, y) = get_ints()
	if x == 0 and y == 0:
		print(0)
		continue
	a = int(sqrt(x * x + y * y))
	if a * a == x * x + y * y or (a - 1) * (a - 1) == x * x + y * y or (a + 1) * (a + 1) == x * x + y * y:
		print(1)
	else:
		print(2)


n = int(input())
for i in range(n):
	c = input().split()
	x = int(c[0])
	y = int(c[1])
	o = ((0 - x) ** 2 + (0 - y) ** 2) ** 0.5
	if x == y == 0:
		print(0)
	elif o == int(o):
		print(1)
	else:
		print(2)


import math
t = input()
i = 1
inp = ''
while i <= int(t):
	k = input()
	ll = k.split(' ')
	k = list(ll)
	dis = math.sqrt(int(k[0]) ** 2 + int(k[1]) ** 2)
	if k == ['0', '0']:
		inp = inp + '0\n'
	elif dis - int(dis) == 0:
		inp = inp + '1\n'
	else:
		inp = inp + '2\n'
	i += 1
print(inp)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x == 0 and y == 0:
		print(0)
	else:
		k = int(math.sqrt(x ** 2 + y ** 2))
		if k ** 2 == x ** 2 + y ** 2:
			print(1)
		else:
			print(2)


import sys

def main():
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
		(x, y) = map(int, sys.stdin.readline().split())
		r = (x ** 2 + y ** 2) ** 0.5
		if x == 0 and y == 0:
			print(0)
		elif int(r) == r:
			print(1)
		else:
			print(2)
main()


import sys
import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, sys.stdin.readline().split())
	x = math.sqrt(a ** 2 + b ** 2)
	if x == 0:
		print(0)
	elif int(x) == x:
		print(1)
	else:
		print(2)


import math
ans = ''
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	if x == 0 and y == 0:
		ans += '0\n'
	elif math.sqrt(x ** 2 + y ** 2) % 1 == 0:
		ans += '1\n'
	else:
		ans += str(2) + '\n'
print(ans)


from collections import Counter
from math import sqrt, ceil, floor, log, gcd
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())):
	(x, y) = inp_multi()
	temp = sqrt(x ** 2 + y ** 2)
	if x == 0 and y == 0:
		print(0)
		continue
	if floor(temp) == ceil(temp):
		print(1)
	else:
		print(2)


import math
t = int(input())
l = []
for i in range(t):
	s = input()
	s = s.split()
	x = int(s[0])
	y = int(s[1])
	if x == 0 and y == 0:
		l.append(0)
	elif math.sqrt(x ** 2 + y ** 2) == int(math.sqrt(x ** 2 + y ** 2)):
		l.append(1)
	else:
		l.append(2)
for i in l:
	print(i)


import math
k = int(input())
for z in range(k):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	root = math.sqrt(int(a) ** 2 + int(b) ** 2)
	ans = 0
	if root == 0:
		pass
	elif root == int(root):
		ans += 1
	else:
		ans += 2
	print(ans)


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


import math
tc = int(input())
for i in range(tc):
	(x2, y2) = map(int, input().split())
	x1 = 0
	y1 = 0
	if x2 == 0 and y2 == 0:
		print(0)
	else:
		distance = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
		if distance == int(distance):
			print(1)
		else:
			print(2)


t = int(input())
answers = [0] * 0
for i in range(t):
	(x, y) = [int(num) for num in input().split()]
	if x == 0 and y == 0:
		answers.append(0)
	elif (x ** 2 + y ** 2) ** 0.5 == int((x ** 2 + y ** 2) ** 0.5):
		answers.append(1)
	else:
		answers.append(2)
for i in answers:
	print(i)


m = []
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	k = (x ** 2 + y ** 2) ** (1 / 2)
	l = int(k)
	if l == k:
		if k == 0:
			m.append(0)
		else:
			m.append(1)
	else:
		m.append(2)
for mo in m:
	print(mo)


import math
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	temp = math.sqrt(x * x + y * y)
	if temp == 0:
		print(0)
	elif temp.is_integer():
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	d = (a * a + b * b) ** 0.5
	if d == 0:
		print(0)
	elif d.is_integer():
		print(1)
	else:
		print(2)


x = int(input())
y = list()
for i in range(x):
	l = list(map(int, input().split()))
	y.append(l)
for i in range(len(y)):
	if y[i][0] == 0 and y[i][1] == 0:
		print(0)
		continue
	if y[i][0] == 0:
		print(1)
		continue
	if y[i][1] == 0:
		print(1)
		continue
	euclid = (y[i][0] ** 2 + y[i][1] ** 2) ** 0.5
	if euclid % 1 == 0:
		print(1)
	else:
		print(2)


n = int(input())
points = [[int(i) for i in input().split()] for _ in range(n)]
squares = set([i * i for i in range(72)])
for (x, y) in points:
	if x == 0 and y == 0:
		print(0)
	elif x * x + y * y in squares:
		print(1)
	else:
		print(2)


import math
t = int(input())
ans = []
for _ in range(t):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	if x == 0 and y == 0:
		ans.append(0)
	elif math.sqrt(x ** 2 + y ** 2) % 1 == 0:
		ans.append(1)
	else:
		ans.append(2)
for x in ans:
	print(x)


import sys
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())
import math

def solve(x, y):
	if x == y == 0:
		return 0
	else:
		d = math.sqrt(x * x + y * y)
		if int(d) == d:
			return 1
		else:
			return 2
count = inp()
for i in range(count):
	[x, y] = inlt()
	steps = solve(x, y)
	print(f'{steps}')


t = int(input())
s = ''
for i in range(0, t):
	(x, y) = map(int, input().split())
	c = (x ** 2 + y ** 2) ** 0.5
	d = int(c)
	if x == 0 and y == 0:
		s = s + '0' + '\n'
	elif d - c == 0:
		s = s + '1' + '\n'
	else:
		s = s + '2' + '\n'
print(s)


import math
out = []

def min_moves():
	y = list(map(int, input().strip().split()))
	dist = math.pow(y[0], 2) + math.pow(y[1], 2)
	eu_dist = math.sqrt(dist)
	if y[0] == 0 and y[1] == 0:
		out.append(0)
	elif eu_dist.is_integer():
		out.append(1)
	else:
		out.append(2)
iter = int(input())
while iter > 0:
	min_moves()
	iter -= 1
for i in range(0, len(out)):
	print(out[i])


import math
t = int(input())
for j in range(t):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	z = math.sqrt(x ** 2 + y ** 2)
	if x == 0 and y == 0:
		print(0)
	elif int(z + 0.5) ** 2 == x ** 2 + y ** 2:
		print(1)
	else:
		print(2)


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


from math import sqrt
test_cases = int(input(''))
destination_points = []
for i in range(test_cases):
	point_input = input('')
	point_tuple = (int(point_input.split(' ')[0]), int(point_input.split(' ')[1]))
	destination_points.append(point_tuple)
for point in destination_points:
	if point == (0, 0):
		print(0)
	elif sqrt(point[0] ** 2 + point[1] ** 2) / 1 == sqrt(point[0] ** 2 + point[1] ** 2) // 1:
		print(1)
	else:
		print(2)


for z in [*open(0)][1:]:
	(u, o) = map(int, z.split())
	print((u | o > 0) + (int((d := ((u * u + o * o) ** 0.5))) < d))


import math

def pitagorizo(x, y):
	resultEcuacion = math.sqrt(pow(0 - x, 2) + pow(0 - y, 2))
	if x == 0 and y == 0:
		print('0')
	elif resultEcuacion == int(resultEcuacion):
		print('1')
	else:
		print('2')
t = int(input())
xy = list()
for i in range(0, t):
	variables = input().split(' ')
	xy.append([int(variables[0]), int(variables[1])])
for i in range(0, t):
	pitagorizo(xy[i][0], xy[i][1])


from os import read
import sys
input = lambda : sys.stdin.readline()

def read_ints():
	return [int(x) for x in input().split(' ')]

def read_int():
	return int(input())
square = set()
for i in range(100):
	square.add(i * i)
T = read_int()
ans = []
for _ in range(T):
	(x, y) = read_ints()
	if x == 0 and y == 0:
		ans.append('0')
		continue
	if x * x + y * y in square:
		ans.append('1')
	else:
		ans.append('2')
print('\n'.join(ans))


from sys import stdin, stdout
from collections import Counter, defaultdict
import math
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	(x, y) = list(map(int, input().strip().split()))
	res = math.sqrt(x ** 2 + y ** 2)
	if x == 0 and y == 0:
		print(0)
		continue
	if math.ceil(res) == math.floor(res):
		print(1)
	else:
		print(2)


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		(x, y) = rv(int)
		if x == 0 and y == 0:
			print(0)
		else:
			d = (x ** 2 + y ** 2) ** 0.5
			if d == floor(d):
				print(1)
			else:
				print(2)
main()


t = int(input())

def getDistance(a, b):
	return float(((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5)
test_cases = []
for i in range(t):
	(a, b) = map(int, input().split())
	test_cases.append([a, b])
for i in range(t):
	current = test_cases[i]
	if current == [0, 0]:
		print(0)
	elif getDistance(current, [0, 0]).is_integer():
		print(1)
	else:
		print(2)


import math
from time import process_time
t = int(input())
ans = []
steps = 0
for tests in range(t):
	(x, y) = map(int, input().split())
	if math.sqrt(x ** 2 + y ** 2).is_integer():
		if x == y == 0:
			steps = 0
			ans.append(steps)
		if x != 0 or y != 0:
			steps = 1
			ans.append(steps)
	if not math.sqrt(x ** 2 + y ** 2).is_integer():
		steps = 2
		ans.append(steps)
print(*ans, sep='\n')


import math
from math import sqrt

def is_square(n):
	return sqrt(n).is_integer()
for t in range(int(input())):
	(x, y) = map(int, input().split())
	if x == 0 and y == 0:
		print(0)
	elif is_square(x * x + y * y):
		print(1)
	else:
		print(2)


import math
cantidadOperaciones = int(input())
i = 0
listaOperaciones = []
while i < cantidadOperaciones:
	operacion = input()
	listaOperaciones.append(operacion)
	i += 1
for elemento in listaOperaciones:
	if len(elemento) == 3:
		x = int(elemento[0])
		y = int(elemento[2])
		numero = math.sqrt(pow(0 - x, 2) + pow(0 - y, 2))
		if x == 0 and y == 0:
			print(0)
		elif numero % 1 == 0:
			print(1)
		else:
			print(2)
	if len(elemento) == 4:
		x = int(elemento[0:2])
		y = int(elemento[2] + elemento[3])
		numero = math.sqrt(pow(0 - x, 2) + pow(0 - y, 2))
		if numero % 1 == 0:
			print(1)
		else:
			print(2)
	if len(elemento) == 5:
		x = int(elemento[0:2])
		y = int(elemento[3] + elemento[4])
		numero = math.sqrt(pow(0 - x, 2) + pow(0 - y, 2))
		if numero % 1 == 0:
			print(1)
		else:
			print(2)


import math
numCases = int(input())
listMoves = []
result = [0] * numCases
for i in range(numCases):
	listMoves.append(list(map(int, input().split())))
for i in range(numCases):
	x = listMoves[i][0]
	y = listMoves[i][1]
	if x == y == 0:
		result[i] = 0
	elif math.sqrt(x * x + y * y).is_integer():
		result[i] = 1
	else:
		result[i] = 2
for i in range(numCases):
	print(result[i])


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


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	num = (x ** 2 + y ** 2) ** 0.5
	if num == int(num):
		if num == 0:
			print(0)
		else:
			print(1)
	else:
		print(2)


import sys
for _ in range(int(input())):
	(x1, y1) = list(map(int, sys.stdin.readline().split()))
	if x1 == y1 == 0:
		print(0)
	else:
		x = (x1 ** 2 + y1 ** 2) ** 0.5
		if int(x) == x:
			print(1)
		else:
			print(2)


import math
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	s = x ** 2 + y ** 2
	if x == y == 0:
		print(0)
	elif math.sqrt(s) == math.isqrt(s):
		print(1)
	else:
		print(2)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x == y == 0:
		print(0)
	elif math.sqrt(x ** 2 + y ** 2).is_integer():
		print(1)
	else:
		print(2)


import math as akjshdjkasdhaaa
for _ in range(int(input())):
	(lskdjalkdasld, ajksdhjksahdkja) = list(map(int, input().split()))
	if lskdjalkdasld == 0 and ajksdhjksahdkja == 0:
		print(0)
	elif akjshdjkasdhaaa.sqrt(lskdjalkdasld ** 2 + ajksdhjksahdkja ** 2) == int(akjshdjkasdhaaa.sqrt(lskdjalkdasld ** 2 + ajksdhjksahdkja ** 2)):
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a == b == 0:
		print(0)
	elif ((0 - a) ** 2 + (0 - b) ** 2) ** 0.5 == int(((0 - a) ** 2 + (0 - b) ** 2) ** 0.5):
		print(1)
	else:
		print(2)


import math
testcases = int(input())
for i in range(testcases):
	(x, y) = map(int, input().split())
	z = x * x
	w = y * y
	q = math.sqrt(z + w)
	if x == 0 and y == 0:
		print(0)
	elif q % int(q) == 0.0:
		print(1)
	else:
		print(2)


def solve():
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		t = a ** 2 + b ** 2
		if a == 0 and b == 0:
			print(0)
		elif int(t ** 0.5) ** 2 == t:
			print(1)
		else:
			print(2)
solve()


import math
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x == 0 and y == 0:
		print(0)
	else:
		n = x ** 2 + y ** 2
		r = math.sqrt(n)
		if int(r + 0.5) ** 2 == n:
			print(1)
		else:
			print(2)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	x = inputs[0]
	y = inputs[1]
	sqrt1 = (x * x + y * y) ** (1 / 2)
	if x == 0 and y == 0:
		print(0)
	elif sqrt1 == int(sqrt1):
		print(1)
	else:
		print(2)


T = int(input())
l = [i * i for i in range(1, 101)]
for t in range(T):
	(a, b) = map(int, input().split())
	c = a * a + b * b
	if c == 0:
		print(0)
	elif c in l:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	s = x ** 2 + y ** 2
	p = pow(s, 1 / 2)
	q = p
	if x == 0 and y == 0:
		print(0)
	elif int(q) == p:
		print(1)
	else:
		print(2)


import math

def euclid(x1, y1, x2, y2):
	k = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
	return k
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 0 and b == 0:
		print(0)
	elif euclid(0, 0, a, b).is_integer():
		print(1)
	else:
		print(2)


ans = []
for i in range(int(input())):
	(x1, y1) = map(int, input().strip().split())
	temp = (x1 ** 2 + y1 ** 2) ** 0.5
	if x1 == 0 and y1 == 0:
		ans.append(0)
	elif int(temp) == temp:
		ans.append(1)
	else:
		ans.append(2)
for i in ans:
	print(i)


import math as m
T = int(input())
for i in range(T):
	list1 = []
	listx = input().split()
	for o in listx:
		list1.append(int(o))
	eucli = m.sqrt(list1[0] * list1[0] + list1[1] * list1[1])
	if list1[0] == 0 and list1[1] == 0:
		print(0)
	elif eucli - int(eucli) == 0:
		print(1)
	else:
		print(2)


from math import sqrt
test = int(input())
ans = []
for x in range(test):
	(x, y) = tuple(map(int, input().split()))
	if sqrt(x ** 2 + y ** 2) == 0:
		ans.append(0)
	elif sqrt(x ** 2 + y ** 2).is_integer():
		ans.append(1)
	else:
		ans.append(2)
for a in ans:
	print(a)


for i in range(int(input())):
	(f, c) = map(int, input().split())
	x = (f ** 2 + c ** 2) ** (1 / 2)
	if f == 0 and c == 0:
		print(0)
	elif x % 1 == 0:
		print(1)
	else:
		print(2)


import math
for j in range(int(input())):
	(a, b) = map(int, input().split())
	c = math.sqrt(pow(a, 2) + pow(b, 2))
	if a == 0 and b == 0:
		print(0)
	elif c - int(c) == 0:
		print(1)
	else:
		print(2)


t = int(input())
import math

def nuqta(a, b):
	if a == 0 and b == 0:
		print(0)
	elif math.sqrt(abs(0 - a) ** 2 + abs(0 - b) ** 2) % 1 == 0:
		print(1)
	else:
		print(2)
for i in range(t):
	(a, b) = map(int, input().split())
	nuqta(a, b)


import math
t = int(input())
while t:
	t = t - 1
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	d = math.sqrt(x ** 2 + y ** 2)
	e = d % 1
	if x == 0 and y == 0:
		print(0)
	elif e == 0:
		print(1)
	else:
		print(2)


from math import pow, sqrt
n = int(input())
for i in range(n):
	res = input().split()
	x = int(res[0])
	y = int(res[1])
	ED = sqrt(pow(-x, 2) + pow(-y, 2))
	if x == y == 0:
		print(0)
	elif ED % 1 == 0:
		print(1)
	else:
		print(2)


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


import math
t = int(input())
for k in range(t):
	(x, y) = map(int, input().split())
	if (x, y) == (0, 0):
		print(0)
	elif math.sqrt(x ** 2 + y ** 2) - int(math.sqrt(x ** 2 + y ** 2)) == 0:
		print(1)
	else:
		print(2)