Chef's favorite game is chess. Today, he invented a new piece and wants to see its strengths.

From a cell (X, Y), the new piece can move to any cell of the chessboard such that its color is different from that of (X, Y).

The new piece is currently located at cell (A, B). Chef wants to calculate the minimum number of steps required to move it to (P, Q).

Note: A chessboard is an 8 \times 8 square board, where the cell at the intersection of the i-th row and j-th column is denoted (i, j). Cell (i, j) is colored white if i+j is even and black if i+j is odd.

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

- The first line of input contains a single integer T denoting the number of test cases. The description of the test cases follows.
- Each test case consists of a single line of input, containing four space-separated integers A, B, P, Q.

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

For each test case, output a single line containing one integer - the minimum number of moves taken by the new piece to reach (P, Q) from (A, B).

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

$1 ≤ T ≤ 5000$
$1 ≤ A,B,P,Q ≤ 8$

----- Sample Input 1 ------ 
3
1 1 8 8
5 7 5 8
3 3 3 3

----- Sample Output 1 ------ 
2
1
0

----- explanation 1 ------ 
Test Case $1$: $(1,1)$ and $(8,8)$ have the same color, so Chef cannot move the new piece in $1$ move. Chef can first move the piece from $(1,1)$ to $(8,1)$ and then from $(8,1)$ to $(8,8)$, thus taking $2$ moves.

Test Case $2$: $(5,7)$ and $(5,8)$ have different colors, so Chef can move the piece from $(5,7)$ to $(5,8)$ in $1$ move.

Difficulty: EASY
Tags: Mathematics

Ad-hoc

Starter code:

Solutions:
for i in range(int(input())):
	a = list(map(int, input().split()))
	if a[0] == a[2] and a[1] == a[3]:
		print(0)
	elif (a[0] + a[1]) % 2 == 0:
		if (a[3] + a[2]) % 2 == 0:
			print(2)
		else:
			print(1)
	elif (a[3] + a[2]) % 2 == 0:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	s = a + b
	d = p + q
	r1 = s % 2
	r2 = d % 2
	if a == p and b == q:
		print(0)
	elif r1 == r2:
		print('2')
	else:
		print('1')


for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	t1 = a + b
	t2 = p + q
	r1 = t1 % 2
	r2 = t2 % 2
	if a == p and b == q:
		print(0)
	elif r1 == r2:
		print('2')
	else:
		print('1')


for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	x = (a + b) % 2
	y = (p + q) % 2
	if a == p and b == q:
		print(0)
	elif x == y:
		print(2)
	else:
		print(1)


def sol(a, b, p, q):
	if not (a == p and b == q):
		if (a + b) % 2 == (p + q) % 2:
			return 2
		else:
			return 1
	else:
		return 0
for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	print(sol(a, b, p, q))


n = int(input())
for i in range(n):
	(a, b, c, d) = map(int, input().split())
	if a == c and b == d:
		print(0)
	elif (a + b) % 2 == 0 and (c + d) % 2 == 0 or ((a + b) % 2 != 0 and (c + d) % 2 != 0):
		print(2)
	else:
		print(1)


for i in range(int(input())):
	x = list(map(int, input().split()))
	h = 0
	c = x[0]
	b = x[1]
	n = x[2]
	m = x[3]
	s = c + b
	l = n + m
	s = s % 2
	l = l % 2
	if c == n and b == m:
		print(h)
	elif s == l:
		print('2')
	else:
		print('1')


for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	sum1 = a + b
	sum2 = p + q
	rem1 = sum1 % 2
	rem2 = sum2 % 2
	if a == p and b == q:
		print(0)
	elif rem1 == rem2:
		print('2')
	else:
		print('1')


for _ in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	if a == p and b == q:
		print(0)
	elif (a + b) % 2 == (p + q) % 2:
		print(2)
	elif (a + b) % 2 != (p + q) % 2:
		print(1)


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


t = int(input())
for i in range(t):
	(a, b, p, q) = list(map(int, input().split()))
	if a == p and b == q:
		print('0')
	elif (a + b) % 2 == (p + q) % 2:
		print('2')
	else:
		print('1')


T = int(input())
while T > 0:
	T -= 1
	(a, b, x, y) = [int(i) for i in input().split()]
	if a == x and y == b:
		print(0)
	elif (a + b) % 2 == (x + y) % 2:
		print(2)
	else:
		print(1)


def re(a, b):
	if (a + b) % 2 == 0:
		return True
	return False
for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if (a, b) == (c, d):
		print(0)
	elif re(a, b) == re(c, d):
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(A, B, P, Q) = map(int, input().split())
	x = (A + B) % 2
	y = (P + Q) % 2
	if A == P and B == Q:
		print(0)
	elif x == 0 and y == 1 or (x == 1 and y == 0):
		print(1)
	elif x == 0 and y == 0 or (x == 1 and y == 1):
		print(2)


for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	f = a + b
	e = c + d
	s = f % 2
	s1 = e % 2
	if a == c and b == d:
		print(0)
	elif s == s1:
		print('2')
	else:
		print('1')


for _ in range(int(input())):
	lit = list(map(int, input().split()))
	if lit[0] == lit[2] and lit[1] == lit[3]:
		print(0)
	else:
		current = lit[0] + lit[1]
		to = lit[2] + lit[3]
		if current % 2 == 0:
			current = 'EVEN'
		else:
			current = 'ODD'
		if to % 2 == 0:
			to = 'EVEN'
		else:
			to = 'ODD'
		if current == to:
			print(2)
		else:
			print(1)


import math
t = int(input())
while t:
	t -= 1
	(a, b, p, q) = [int(x) for x in input().split()]
	if a == p and b == q:
		print(0)
	elif abs(a - p) + abs(b - q) & 1:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(cute, pie, janu, buji) = map(int, input().split())
	sin = cute + pie
	din = janu + buji
	v1 = sin % 2
	v2 = din % 2
	if cute == janu and pie == buji:
		print(0)
	elif v1 == v2:
		print('2')
	else:
		print('1')


t = int(input())
while t > 0:
	(a, b, x, y) = map(int, input().split())
	p = a + b
	q = x + y
	r1 = p % 2
	r2 = q % 2
	if a == x and b == y:
		print(0)
	elif r1 == r2:
		print('2')
	else:
		print('1')
	t -= 1


for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	Is = a + b
	fs = p + q
	if a == p and b == q:
		print(0)
	elif Is % 2 == 0 and fs % 2 == 0 or (Is % 2 != 0 and fs % 2 != 0):
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	x = a + b
	y = p + q
	m = x % 2
	n = y % 2
	if a == p and b == q:
		print(0)
	elif m == n:
		print(2)
	else:
		print(1)


for x in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	current = (a + b) % 2
	expected = (p + q) % 2
	if current == expected:
		not_same = False
	else:
		not_same = True
	if a == p and q == b:
		print(0)
	elif not_same:
		print(1)
	else:
		print(2)


T = int(input())
for i in range(T):
	(A, B, P, Q) = map(int, input().split())
	if A == P and B == Q:
		print(0)
	elif (A + B) % 2 == (P + Q) % 2:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	(a, b, p, q) = map(int, input().split())
	c = a + b
	d = p + q
	if a == p and b == q:
		print(0)
	elif (c + d) % 2 == 0:
		print(2)
	elif (c + d) % 2 != 0:
		print(1)


t = int(input())
for _ in range(t):
	steps = 0
	(a, b, p, q) = [int(i) for i in input().split()]
	if a == p and b == q:
		steps = 0
	elif (a + b) % 2 == (p + q) % 2:
		steps = 2
	else:
		steps = 1
	print(steps)


n = int(input())
for i in range(n):
	(a, b, p, q) = map(int, input().split())
	if (a, b) == (p, q):
		print(0)
	elif (a + b) % 2 == (p + q) % 2:
		print(2)
	elif (a + b) % 2 != (p + q) % 2:
		print(1)
	else:
		pass


T = int(input())
for i in range(T):
	(X, Y, P, Q) = map(int, input().split())
	if X == P and Y == Q:
		print(0)
	elif (X + Y) % 2 == (P + Q) % 2:
		print(2)
	elif (X + Y) % 2 != (P + Q) % 2:
		print(1)


def color(a, b):
	ab = ''
	if a % 2 == 0 and b % 2 == 0:
		ab = 'white'
	elif a % 2 != 0 and b % 2 != 0:
		ab = 'white'
	else:
		ab = 'black'
	return ab
for _ in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	ab = color(a, b)
	pq = color(p, q)
	if a == p and b == q:
		print(0)
		continue
	if ab == pq:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	l = [a, b]
	m = [c, d]
	k = [[a - 1, b], [a + 1, b], [a, b + 1], [a, b - 1]]
	if m == l:
		print(0)
	elif m in k or sum(m) % 2 != sum(l) % 2:
		print(1)
	else:
		print(2)


for t in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	s = a + b
	r = p + q
	y = s % 2
	x = r % 2
	if a == p and b == q:
		print('0')
	elif y == x:
		print('2')
	else:
		print('1')


a = int(input())
for i in range(a):
	(p, q, r, s) = list(map(int, input().split()))
	b = p + q
	c = r + s
	kr = b % 2
	ha = c % 2
	if p == r and q == s:
		print(0)
	elif kr == ha:
		print(2)
	else:
		print(1)


m = int(input())
while m > 0:
	(a, b, c, d) = map(int, input().split())
	if a == c and b == d:
		print(0)
	elif (a + b) % 2 == (c + d) % 2:
		print(2)
	else:
		print(1)
	m = m - 1


for t in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if a == c and b == d:
		print(0)
	elif (a + b) % 2 == (c + d) % 2:
		print(2)
	else:
		print(1)


for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	r = a + b
	s = c + d
	r1 = r % 2
	r2 = s % 2
	if a == c and b == d:
		print('0')
	elif r1 == r2:
		print('2')
	else:
		print('1')


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


def func(l):
	sum1 = l[0] + l[1]
	sum2 = l[2] + l[3]
	if l[0] == l[2] and l[1] == l[3]:
		return 0
	elif sum1 % 2 == 0 and sum2 % 2 == 0 or (sum1 % 2 != 0 and sum2 % 2 != 0):
		return 2
	elif sum1 % 2 == 0 and sum2 % 2 != 0 or (sum1 % 2 != 0 and sum2 % 2 == 0):
		return 1
n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	print(func(l))


t = int(input())
for i in range(t):
	(a, b, x, y) = map(int, input().split())
	if a == x and b == y:
		print('0')
	elif (a + b) % 2 == 0 and (x + y) % 2 == 0:
		print('2')
	elif (a + b) % 2 != 0 and (x + y) % 2 != 0:
		print('2')
	elif (a + b) % 2 != 0 or (x + y) % 2 != 0:
		print('1')


t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	(i, j) = ((l[0] + l[1]) % 2, (l[2] + l[3]) % 2)
	if i == j:
		if l[0] == l[2] and l[1] == l[3]:
			print(0)
		else:
			print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	(x1, x2, y1, y2) = map(int, input().split())
	if (x1 + x2) % 2 == 0:
		cell1 = 'WHITE'
	else:
		cell1 = 'BLACK'
	if (y1 + y2) % 2 == 0:
		cell2 = 'WHITE'
	else:
		cell2 = 'BLACK'
	if cell1 != cell2:
		print('1')
	elif (x1, x2) == (y1, y2):
		print('0')
	else:
		print('2')