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>
import java.io.*;
    import java.util.*;
    import java.math.*;
    import java.lang.*;
     
    import static java.lang.Math.*;
     
    public class Cf182 implements Runnable 
    {
    	static class InputReader 
    	{
    		private InputStream stream;
    		private byte[] buf = new byte[1024];
    		private int curChar;
    		private int numChars;
    		private SpaceCharFilter filter;
    		private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		public InputReader(InputStream stream) 
    		{
    			this.stream = stream;
    		}
    		
    		public int read()
    		{
    			if (numChars==-1) 
    				throw new InputMismatchException();
                
    			if (curChar >= numChars) 
    			{
    				curChar = 0;
    				try
    				{
    					numChars = stream.read(buf);
    				}
    				catch (IOException e)
    				{
    					throw new InputMismatchException();
    				}
                    
    				if(numChars <= 0)               
    					return -1;
    			}
    			return buf[curChar++];
    		}
         
    		public String nextLine()
    		{
    			String str = "";
    			try
    			{
    				str = br.readLine();
    			}
    			catch (IOException e)
    			{
    				e.printStackTrace();
    			}	
    			return str;
    		}
    		public int nextInt() 
    		{
    			int c = read();
                
    			while(isSpaceChar(c)) 
    				c = read();
    		
    			int sgn = 1;
            
    			if (c == '-') 
    			{
    				sgn = -1;
    				c = read();
    			}
                
    			int res = 0;
    			do
    			{
    				if(c<'0'||c>'9') 
    					throw new InputMismatchException();
    				res *= 10;
    				res += c - '0';
    				c = read();
    			}
    			while (!isSpaceChar(c)); 
            
    			return res * sgn;
    		}
            
    		public long nextLong() 
    		{
    			int c = read();
    			while (isSpaceChar(c))
    				c = read();
    			int sgn = 1;
    			if (c == '-')
    			{
    				sgn = -1;
    				c = read();
    			}
    			long res = 0;
    			
    			do 
    			{
    				if (c < '0' || c > '9')
    					throw new InputMismatchException();
    				res *= 10;
    				res += c - '0';
    				c = read();
    			}	
    			while (!isSpaceChar(c));
    				return res * sgn;
    		}
    		
    		public double nextDouble() 
    		{
    			int c = read();
    			while (isSpaceChar(c))
    				c = read();
    			int sgn = 1;
    			if (c == '-')
    			{
    				sgn = -1;
    				c = read();
    			}
    			double res = 0;
    			while (!isSpaceChar(c) && c != '.') 
    			{
    				if (c == 'e' || c == 'E')
    					return res * Math.pow(10, nextInt());
    				if (c < '0' || c > '9')
    					throw new InputMismatchException();
    				res *= 10;
    				res += c - '0';
    				c = read();
    			}
    			if (c == '.') 
    			{
    				c = read();
    				double m = 1;
    				while (!isSpaceChar(c))
    				{
    					if (c == 'e' || c == 'E')
    						return res * Math.pow(10, nextInt());
    					if (c < '0' || c > '9')
    						throw new InputMismatchException();
    					m /= 10;
    					res += (c - '0') * m;
    					c = read();
    				}
    			}
    			return res * sgn;
    		}
        
    		public String readString() 
    		{
    			int c = read();
    			while (isSpaceChar(c))
    				c = read();
    			StringBuilder res = new StringBuilder();
    			do 
    			{
    				res.appendCodePoint(c);
    				c = read();
    			} 
    			while (!isSpaceChar(c));
                
    			return res.toString();
    		}
         
    		public boolean isSpaceChar(int c) 
    		{
    			if (filter != null)
    				return filter.isSpaceChar(c);
    			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    		}
         
    		public String next()
    		{
    			return readString();
    		}
            
    		public interface SpaceCharFilter
    		{
    			public boolean isSpaceChar(int ch);
    		}
    	}
    	public static void main(String args[]) throws Exception 
    	{
    		new Thread(null, new Cf182(),"Main",1<<27).start();
    	}	
    	
    	public static long gcd(long a, long b) 
    	{ 
    		if (a == 0) 
    			return b; 
    		return gcd(b % a, a); 
    	} 
    	//  array sorting by colm
    public static void sortbyColumn(int arr[][], int col) 
        { 
            
            Arrays.sort(arr, new Comparator<int[]>() { 
                
              @Override
              public int compare(final int[] entry1,  
                                 final int[] entry2) { 
      
               
                if (entry1[col] > entry2[col]) 
                    return 1; 
                else
                    return -1; 
              } 
            });  
        } 
    	
    	// gcd
      
    	public static long findGCD(long arr[], int n) 
    	{ 
    		long result = arr[0]; 
    		for (int i = 1; i < n; i++) 
    			result = gcd(arr[i], result); 
    		return result; 
    	}
    	// fibonaci
    	static int fib(int n) 
        { 
            int a = 0, b = 1, c; 
            if (n == 0) 
                return a; 
            for (int i = 2; i <= n; i++) 
            { 
                c = a + b; 
                a = b; 
                b = c; 
            } 
            return b; 
        } 
        
    // sort a string
        public static String sortString(String inputString) 
        { 
            
            char tempArray[] = inputString.toCharArray(); 
              
             
            Arrays.sort(tempArray); 
              
             
            return new String(tempArray); 
        } 
        // pair function
        
        // list.add(new Pair<>(sc.nextInt(), i + 1));
        //     Collections.sort(list, (a, b) -> Integer.compare(b.first, a.first));
        private static class Pair<F, S> {
     
            private F first;
     
            private S second;
     
            public Pair() {}
     
            public Pair(F first, S second) {
                this.first = first;
                this.second = second;
            }
        }
        
    	// SortedArrayList<Integer> test = new SortedArrayList<Integer>();
        // test.insert(5); 
                public static class SortedArrayList<T> extends ArrayList<T> {
            
                @SuppressWarnings("unchecked")
                public void insert(T value) {
                    add(value);
                    Comparable<T> cmp = (Comparable<T>) value;
                    for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
                        Collections.swap(this, i, i-1);
                }
            }
        
    	
    	public static boolean equalsum(int arr[], int n,int sum)
    	{
    	    boolean dp[][] = new boolean[n + 1][sum + 1];
    	    
    	    for(int i=0;i<=n;i++)
            {
                for(int j=0;j<=sum;j++)
                {
                    if(j==0)
                        dp[i][j] = true;
                    else if(i==0)
                        dp[i][j] = false;
                    else if(arr[i-1]>j)
                        dp[i][j] = dp[i-1][j];
                    else
                        dp[i][j] = dp[i-1][j] | dp[i-1][j-arr[i-1]];
                }
            }
            return dp[n][sum];
    	}
    	
    	public void run()
    	{
    		InputReader sc = new InputReader(System.in);
    		PrintWriter w = new PrintWriter(System.out);
    		
    		int t = sc.nextInt();
    		
    		while(t--!=0)
    		{
    		    int n = sc.nextInt();
    		    int k = sc.nextInt();
    		    
    		    if(k>=n)
    		        w.println(Math.abs(n-k));
    		    else
    		    {
        		    if( (n%2) != (k%2) )
        		        w.println("1");
        		    else
        		        w.println("0");
    		    }
    		}
    		
            w.flush();
    	    w.close();
    	}
    }