We have a point A with coordinate x = n on OX-axis. We'd like to find an integer point B (also on OX-axis), such that the absolute difference between the distance from O to B and the distance from A to B is equal to k.

<image> The description of the first test case.

Since sometimes it's impossible to find such point B, we can, in one step, increase or decrease the coordinate of A by 1. What is the minimum number of steps we should do to make such point B exist?

Input

The first line contains one integer t (1 ≤ t ≤ 6000) — the number of test cases.

The only line of each test case contains two integers n and k (0 ≤ n, k ≤ 10^6) — the initial position of point A and desirable absolute difference.

Output

For each test case, print the minimum number of steps to make point B exist.

Example

Input


6
4 0
5 8
0 1000000
0 0
1 0
1000000 1000000


Output


0
3
1000000
0
1
0

Note

In the first test case (picture above), if we set the coordinate of B as 2 then the absolute difference will be equal to |(2 - 0) - (4 - 2)| = 0 and we don't have to move A. So the answer is 0.

In the second test case, we can increase the coordinate of A by 3 and set the coordinate of B as 0 or 8. The absolute difference will be equal to |8 - 0| = 8, so the answer is 3.

<image>
# def countFreq(pat, txt): 
#     M = len(pat) 
#     N = len(txt) 
#     res = 0
      
#     # A loop to slide pat[] one by one  
#     for i in range(N - M + 1): 
          
#         # For current index i, check  
#         # for pattern match  
#         j = 0
#         for j in range(M): 
#             if (txt[i + j] != pat[j]): 
#                 break
  
#         if (j == M - 1): 
#             res += 1
#             j = 0
#     return res 



# for _ in range(int(input())):
# 	n = int(input())
# 	s = str(input())
# 	t = "abacaba"

# 	res = countFreq(t,s)
# 	if res ==1:
# 		print("yes")
# 		s=list(s)
# 		srr=""
# 		for i in range(n):
# 			if s[i]=="?":
# 				s[i]="d"
# 		print(srr.join(s))
# 	elif res >1:
# 		print("no")

# 	else:
# 		i,j=0,0
# 		s = list(s)
# 		t = list(t)
# 		while i<n and j<7:
# 			if s[i]==t[j]:
# 				i+=1
# 				j+=1
# 			elif s[i]=="?":
# 				s[i]=t[j]
# 				i+=1
# 				j+=1
# 			else:
# 				j=0
# 				i+=1
# 		if j==7:
# 			print("yes")
# 			srr=""
# 			for q in range(n):
# 				if s[q]=="?":
# 					s[q]=="d"
# 			print(srr.join(s))
# 		else:
# 			print("no")


# results=[]
# target_length =2
# arr = [1,2,3]

# def combination(i,path):

# 	if len(path)==target_length:
# 		results.append(path[:])
# 		return 

# 	for x in range(i,len(arr)):
# 		path.append(arr[x])

# 		combination(x,path)

# 		path.pop()

# combination(0,[])
# print(results)


# def permutation(path):
# 	if len(path)==len(arr):
# 		results.append(path[:])
# 		return

# 	for i in range(0,len(arr)):
# 		if arr[i] not in path:
# 			path.append(arr[i])

# 			permutation(path)

# 			path.pop()
# permutation([])
# print(results)


# for _ in range(int(input())):
#     n = int(input())
#     a = list(map(int,input().split()))
#     ans = list('a'*(max(a)+1))
#     for i in range(n):
#         print(''.join(ans))
#         ans[a[i]] = chr(ord(ans[a[i]])+1)
#         if ans[a[i]]>'z':
#             ans[a[i]]='a'
 
#     print(''.join(ans))

# for _ in range(int(input())):
# 	n = int(input())
# 	a = list(map(int,input().split()))
# 	b = list(map(int,input().split()))
# 	result=0
# 	a_min=min(a)
# 	b_min=min(b)
# 	for i in range(n):
# 		result+= max(a[i]-a_min,b[i]-b_min)

# 	print(result)

# def pair(sum_arr,a,sum):
# 	l = 0
# 	r = len(a)-1
# 	c=0
# 	while l<r:
# 		if a[l]+a[r]==sum:
# 			c+=1
# 			l+=1
# 			r-=1
# 		elif a[l]+a[r]>sum:
# 			r-=1
# 		else:
# 			l+=1
# 	return c


# MAximum subarray with length K
# def foo(A,K):
# 	p = [0]
# 	for x in A:
# 		p.append(p[-1]+x)
# 	i = 0
# 	j = i+K
# 	maxsum = 0
# 	interval = [0,0]
# 	while j<len(p):
# 		if p[j]-p[i]> maxsum:
# 			maxsum = p[j]-p[i]
# 			interval[0] = i
# 			interval[1] = j
# 		j+=1
# 		i+=1
# 	return A[interval[0]:interval[1]]


# for _ in range(int(input())):
# 	K = int(input())
# 	A = list(map(int,input().split()))
# 	print(foo(A,K))





# def minAbs(nums):
# 	nums.sort()
# 	s = sum(nums)//2
# 	n = len(nums)
# 	dp = [[0 for _ in range(s+1)] for _ in range(n+1)]

# 	for i in range(1,n+1):
# 		for j in range(1,s+1):

# 			if j < nums[i-1]:
# 				dp[i][j] = dp[i-1][j]
# 			else:
# 				dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1])


# 	return abs(sum(nums)-2*dp[-1][-1])

# nums = list(map(int,input().split()))
# print(minAbs(nums))


# from collections import defaultdict
# def booking(data):
# 	d = defaultdict(int)
# 	max_booked = data[0][1:]
# 	for ele in data:
# 		key=ele[1:]
# 		if ele[0]=="+":
# 			d[key]+=1
# 		if d[key] > d[max_booked]:
# 			max_booked = key
# 		elif d[key]==d[max_booked]:
# 			max_booked = min(key,max_booked)
# 	return max_booked

# data = ["+3Z", "+3E", "-3Z", "+4F", "+3Z", "-3E","+3E","+1B","-3E"]
# print(booking(data))


# from collections import defaultdict
# def triplets(arr,target):

# 	arr = [x for x in arr if x!=0 and target%x==0]

# 	arr.sort()
# 	n = len(arr)
# 	triplet_seen = defaultdict(bool)
# 	count = defaultdict(int)

# 	for key in arr:
# 		count[key]+=1

# 	total_count = 0

# 	def combinations(x,y,z):
# 		if x==y:
# 			if y==z:
# 				return (count[x]*(count[y]-1)*(count[z]-2))//6
# 			else:
# 				return (count[x]*(count[y]-1)//2)*(count[z])

# 		elif y==z:
# 			return count[x]*(((count[y])*(count[z]-1))//2)

# 		else:
# 			return count[x]*count[y]*count[z]


# 	for i in range(len(arr)-2):
# 		for j in range(i+1,len(arr)-1):

# 			if target % (arr[i]*arr[j])==0:
# 				toFind = target // (arr[i]*arr[j])

# 				if toFind>=arr[i] and toFind>=arr[j] and triplet_seen[(arr[i],arr[j],toFind)]==False:
# 					triplet_seen[(arr[i],arr[j],toFind)] = True
# 					total_count+= combinations(arr[i],arr[j],toFind)

# 	return total_count

# print(triplets([1, 31, 3, 1, 93, 3, 31, 1, 93],93))














# for _ in range(int(input())):
# 	n = int(input())
# 	for i in range(1,n+1):
# 		print(i,end=" ")
# 	print()

# def fix(a,n,m):
# 	count = 0
# 	for i in range(n):
# 		if a[i][m-1]=="R":
# 			count+=1
# 	for j in range(m):
# 		if a[n-1][j]=="D":
# 			count+=1
# 	return count


# for _ in range(int(input())):
# 	n,m = map(int,input().split())
# 	matrix=[]
# 	for i in range(n):
# 		a= list(input())
# 		matrix.append(a)
# 	print(fix(matrix,n,m))



for _ in range(int(input())):
	n,k = map(int,input().split())
	
	if k<=n and n%2==0 and k%2==0:
		print(0)

	elif k<=n and n%2==0 and k%2!=0:
		print(1)

	elif k<=n and n%2!=0 and k%2==0:
		print(1)

	elif k<=n and n%2!=0 and k%2!=0:
		print(0) 

	else:
		print(abs(k-n))