Akash is stuck in a N \times N grid, where N is odd. The rows of the grid are numbered 1 to N from top to bottom, and the columns are numbered 1 to N from left to right. The cell at the intersection of the i-th row and j-th column will be denoted (i, j).

The grid has a unique center cell — ((N+1)/2, (N+1)/2). For example, when N = 5 the center is cell (3, 3).

Akash is currently at cell (x_{s}, y_{s}). He would like to reach the exit of the grid, which is located at the center. It is guaranteed that (x_{s}, y_{s}) is not the center.

Suppose Akash is at cell (x, y). He can make the following movements:
He can freely move along diagonals, i.e, to cells (x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1) 
He can move one step horizontally or vertically with the cost of 1 gold coin, i.e, to cells (x, y-1), (x, y+1), (x-1, y), (x+1, y)

Note that Akash is not allowed to make a move that will take him out of bounds of the grid.

Akash would like to minimize the number of coins required to reach the center. Please help him find this number.

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

- The first line of input contains 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 three space-separated integers N, x_{s}, y_{s} — the size of the grid and the coordinates of Akash's starting cell.

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

For each test case, output in a single line the minimum number of gold coins Akash needs to reach the center.

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

$1 ≤ T ≤ 10^{4}$
$3 ≤ N < 2 \cdot 10^{4}$
$N$ is always odd.
$1 ≤ x_{s}, y_{s} ≤ N$

----- Sample Input 1 ------ 
2
3 2 1
5 3 1
----- Sample Output 1 ------ 
1
0

----- explanation 1 ------ 
Test case 1: For a $3 \times 3$ grid, the center is at $(2,2)$. It is not possible to reach $(2,2)$ from $(2,1)$ using only diagonal moves. So, Akash will directly go to the center using 1 gold coin.

Test case 2: $N = 5$, so the center is $(3, 3)$. Akash can go from $(3,1)$ to $(2,2)$ with a diagonal move, then from $(2,2)$ to $(3, 3)$ with another diagonal move. So, he needs zero coins.

.png)

Difficulty: EASY

Starter code:

Solutions:
num_test_cases = int(input())
while num_test_cases > 0:
	(n, r, c) = map(int, input().split())
	parity = (r + c) % 2
	if parity == 0:
		print(0)
	else:
		print(1)
	num_test_cases -= 1


t = int(input())
for i in range(t):
	(N, x, y) = map(int, input().split())
	if (x + y) % 2 == 0:
		print(0)
	else:
		print((x + y) % 2)


for _ in range(int(input())):
	(N, x, y) = [int(x) for x in input().split()]
	print((x + y) % 2)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	print((x + y) % 2)


for _ in range(int(input())):
	(n, x, y) = [int(i) for i in input().split()]
	if x % 2 == 0 and y % 2 != 0 or (x % 2 != 0 and y % 2 == 0):
		print(1)
	else:
		print(0)


t = int(input())
while t > 0:
	t -= 1
	data = list(map(int, input().split(' ')))
	n = data[0]
	x = data[1]
	y = data[2]
	center = int((n + 1) / 2)
	xdiff = abs(center - x)
	ydiff = abs(center - y)
	if (xdiff + ydiff) % 2 == 0:
		print('0')
	else:
		print('1')


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


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


T = int(input())
for i in range(T):
	(n, x, y) = map(int, input().split())
	if (x + y) % 2 == 0:
		print('0')
	else:
		print('1')


for tc in range(int(input())):
	(n, x, y) = map(int, input().split())
	xc = (n + 1) // 2
	yc = (n + 1) // 2
	difx = abs(xc - x)
	dify = yc - y
	tdif = difx + dify
	print(tdif % 2)


t = int(input())
while t != 0:
	(n, x, y) = map(int, input().split())
	if (x + y) % 2 == 0:
		print(0)
	else:
		print(1)
	t -= 1


t = int(input())
while t:
	(n, x, y) = map(int, input().split())
	n = (n + 1) / 2
	n = int(n)
	a = n - x
	b = n - y
	if a < 0:
		a = a * -1
		a = int(a)
	if b < 0:
		b = b * -1
		b = int(b)
	if a - b > 0:
		if (a - b) % 2 == 0:
			print(0)
		else:
			print(1)
	elif (b - a) % 2 == 0:
		print(0)
	else:
		print(1)
	t = t - 1


a = int(input(''))
for i in range(a):
	(N, x, y) = [int(x) for x in input('').split()]
	print((x + y) % 2)


for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	print((b + c) % 2)


for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	ctr = (a + 1) / 2
	ps = b + c
	if ctr % 2 == 0 and ps % 2 != 0:
		print(1)
	elif ctr % 2 == 0 and ps % 2 == 0:
		print(0)
	elif ctr % 2 != 0 and ps % 2 != 0:
		print(1)
	else:
		print(0)


t = int(input())
while t:
	(a, b, c) = map(int, input().split())
	if (b + c) % 2 == 0:
		print(0)
	else:
		print(1)
	t -= 1


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


import sys
for _ in range(int(sys.stdin.readline())):
	(n, x, y) = map(int, sys.stdin.readline().split())
	if x % 2 == 0 and y % 2 == 1 or (x % 2 == 1 and y % 2 == 0):
		sys.stdout.write(str(1) + '\n')
	else:
		sys.stdout.write(str(0) + '\n')


import sys

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

def intinp():
	return int(sys.stdin.readline())

def println(n):
	return sys.stdout.write(str(n) + '\n')

def solve(n, x, y):
	if x % 2 == 0 and y % 2 == 1 or (x % 2 == 1 and y % 2 == 0):
		println(1)
	else:
		println(0)
for _ in range(intinp()):
	(n, x, y) = intmapinp()
	solve(n, x, y)


for _ in range(int(input())):
	(N, x, y) = [int(a) for a in input().split(' ')]
	print(1 if x % 2 == 0 and y % 2 == 1 or (x % 2 == 1 and y % 2 == 0) else 0)


T = int(input())
for _ in range(T):
	(N, x, y) = [int(a) for a in input().split(' ')]
	semiMod = True if x % 2 == 0 and y % 2 == 1 or (x % 2 == 1 and y % 2 == 0) else False
	if semiMod:
		print(1)
	else:
		print(0)


T = int(input())
for _ in range(T):
	(N, x, y) = map(int, input().split())
	print(int((N + 1 - x - y) % 2 == 1))


for _ in range(int(input())):
	(n, xs, ys) = map(int, input().split())
	c = (n + 1) // 2
	d = abs(xs - c) % 2 + abs(ys - c) % 2
	if d == 1:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	(x, e, f) = map(int, input().split())
	if (e + f) % 2 == 0:
		print(0)
	else:
		print(1)


t = int(input())
for a in range(t):
	(n, x, y) = map(int, input().split(' '))
	(x1, y1) = ((n + 1) / 2, (n + 1) / 2)
	if (x1 - x) % 2 == 0:
		a = 'even'
	else:
		a = 'odd'
	if (y1 - y) % 2 == 0:
		b = 'even'
	else:
		b = 'odd'
	if a == b:
		print(0)
	else:
		print(1)


for testcase in range(int(input())):
	(n, xs, ys) = map(int, input().split())
	print(abs(xs - ys) % 2)


for testcase in range(int(input())):
	(n, xs, ys) = map(int, input().split())
	coins = 1
	if xs % 2 == 1:
		if ys % 2 == 1:
			coins = 0
	elif ys % 2 == 0:
		coins = 0
	print(coins)


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


for t in range(int(input())):
	(n, x, y) = map(int, input().split(' '))
	if x % 2 == 0 and y % 2 != 0 or (x % 2 != 0 and y % 2 == 0):
		print('1')
	else:
		print('0')


vishnesh = int(input())
for vish in range(vishnesh):
	(n, a, b) = map(int, input().split())
	if (a - b) % 2:
		print(1)
	else:
		print(0)


t = input()
for c in range(0, int(t)):
	(n, s_i, s_j) = map(int, input().split())
	(mid_i, mid_j) = (n // 2 + 1, n // 2 + 1)
	diff_i = s_i - mid_i
	(curr_i, curr_j) = (mid_i, s_j + diff_i)
	if (curr_j - mid_j) % 2 == 0:
		print(0)
	else:
		print(1)


import sys

def check(y, cy):
	if (y - cy) % 2 == 0:
		print('0')
	else:
		print('1')
t = int(input())
while t:
	(n, x, y) = map(int, input().split(' '))
	(cx, cy) = (int((n + 1) / 2), int((n + 1) / 2))
	if x == cx:
		check(y, cy)
	else:
		d = abs(cx - x)
		if y <= cy:
			check(y + d, cy)
		else:
			check(y - d, cy)
	t -= 1


t = int(input())
while t:
	(n, s_i, s_j) = map(int, input().split())
	(mid_i, mid_j) = (n // 2 + 1, n // 2 + 1)
	diff_i = s_i - mid_i
	(curr_i, curr_j) = (mid_i, s_j + diff_i)
	if (curr_j - mid_j) % 2 == 0:
		print(0)
	else:
		print(1)
	t -= 1


tests = int(input())
for i in range(tests):
	(n, x, y) = map(int, input().split())
	middle = (n + 1) // 2
	x_diff = abs(x - middle)
	y_diff = abs(y - middle)
	minimum = min(x_diff, y_diff)
	steps = x_diff - minimum + y_diff - minimum
	if steps & 1:
		print(1)
	else:
		print(0)


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


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	p = a // 2 + 1
	q = p
	if (p - b) % 2 == 0 and (q - c) % 2 == 0 or (p - b + (q - c)) % 2 == 0:
		print(0)
	else:
		print(1)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	ex = (n + 1) // 2
	ey = ex
	result = 1
	if x % 2 == 0 and y % 2 == 0:
		result = 0
	elif x % 2 == 1 and y % 2 == 1:
		result = 0
	print(result)


T = int(input())
for i in range(T):
	(N, x_s, y_s) = [int(n) for n in input().split()]
	print(abs(x_s - y_s) % 2)


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


T = int(input())
for i in range(T):
	(a, b, c) = map(int, input().split())
	if (b - c) % 2 == 0:
		print(0)
	else:
		print(1)


t = int(input())
while t:
	t -= 1
	(n, x, y) = map(int, input().split())
	x1 = (n + 1) // 2
	y1 = x1
	if x1 <= x and y1 <= y:
		x = x - (y - y1)
		y = y1
		if (x - x1) % 2 == 0:
			print(0)
		else:
			print(1)
	elif x1 <= x and y1 >= y:
		x = x - (y1 - y)
		y = y1
		if (x - x1) % 2 == 0:
			print(0)
		else:
			print(1)
	elif x1 >= x and y1 <= y:
		x = x + (y - y1)
		y = y1
		if (x - x1) % 2 == 0:
			print(0)
		else:
			print(1)
	elif x1 >= x and y1 >= y:
		x = x + (y1 - y)
		y = y1
		if (x - x1) % 2 == 0:
			print(0)
		else:
			print(1)


for t in range(int(input())):
	(n, xs, ys) = map(int, input().split())
	if (xs + ys) % 2 == 0:
		c = 0
	else:
		c = 1
	print(c)


for i in range(int(input())):
	nums = list(map(int, input().split()))
	v = nums[1]
	w = nums[2]
	l = v + w
	if l % 2 == 0:
		print(0)
	else:
		print(1)


t = int(input())
for _ in range(t):
	a = list(map(int, input().split()))
	if (a[1] + a[2]) % 2 == 1:
		print('1')
	else:
		print('0')


t = int(input())
for l in range(t):
	(n, x, y) = map(int, input().split())
	(mx, my) = (int((n + 1) / 2), int((n + 1) / 2))
	if x % 2 == 0:
		if y % 2 == 0:
			print(0)
		else:
			print(1)
	elif x % 2 == 1:
		if y % 2 == 1:
			print(0)
		else:
			print(1)