The grasshopper is located on the numeric axis at the point with coordinate x_0.

Having nothing else to do he starts jumping between integer points on the axis. Making a jump from a point with coordinate x with a distance d to the left moves the grasshopper to a point with a coordinate x - d, while jumping to the right moves him to a point with a coordinate x + d.

The grasshopper is very fond of positive integers, so for each integer i starting with 1 the following holds: exactly i minutes after the start he makes a jump with a distance of exactly i. So, in the first minutes he jumps by 1, then by 2, and so on.

The direction of a jump is determined as follows: if the point where the grasshopper was before the jump has an even coordinate, the grasshopper jumps to the left, otherwise he jumps to the right.

For example, if after 18 consecutive jumps he arrives at the point with a coordinate 7, he will jump by a distance of 19 to the right, since 7 is an odd number, and will end up at a point 7 + 19 = 26. Since 26 is an even number, the next jump the grasshopper will make to the left by a distance of 20, and it will move him to the point 26 - 20 = 6.

Find exactly which point the grasshopper will be at after exactly n jumps.

Input

The first line of input contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Each of the following t lines contains two integers x_0 (-10^{14} ≤ x_0 ≤ 10^{14}) and n (0 ≤ n ≤ 10^{14}) — the coordinate of the grasshopper's initial position and the number of jumps.

Output

Print exactly t lines. On the i-th line print one integer — the answer to the i-th test case — the coordinate of the point the grasshopper will be at after making n jumps from the point x_0.

Example

Input


9
0 1
0 2
10 10
10 99
177 13
10000000000 987654321
-433494437 87178291199
1 0
-1 1


Output


-1
1
11
110
190
9012345679
-87611785637
1
0

Note

The first two test cases in the example correspond to the first two jumps from the point x_0 = 0. 

Since 0 is an even number, the first jump of length 1 is made to the left, and the grasshopper ends up at the point 0 - 1 = -1.

Then, since -1 is an odd number, a jump of length 2 is made to the right, bringing the grasshopper to the point with coordinate -1 + 2 = 1.
9
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

2
2
2
2
2
2
2
2
2

//   package faltu;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//import java.security.KeyStore.Entry;
import java.util.*;
import java.util.Map.Entry;

public class Main {
    static long LowerBound(long[] a2, long x) { // x is the target value or key
	  int l=-1,r=a2.length;
	  while(l+1<r) {
	    int m=(l+r)>>>1;
	    if(a2[m]>=x) r=m;
	    else l=m;
	  }
	  return r;
	}
    static int UpperBound(int a[], int x) {// x is the key or target value
    int l=-1,r=a.length;
    while(l+1<r) {
       int m=(l+r)>>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }
    public static long getClosest(long val1, long val2,long target)
	{
		if (target - val1 >= val2 - target)
		return val2;       
		else
		return val1;       
	}
    public static long findClosest(long arr[], long target)
    {
        int n = arr.length;
 
        // Corner cases
        if (target <= arr[0])
            return arr[0];
        if (target >= arr[n - 1])
            return arr[n - 1];
 
        // Doing binary search
        int i = 0, j = n, mid = 0;
        while (i < j) {
            mid = (i + j) / 2;
 
            if (arr[mid] == target)
                return arr[mid];
 
            /* If target is less than array element,
               then search in left */
            if (target < arr[mid]) {
        
                // If target is greater than previous
                // to mid, return closest of two
                if (mid > 0 && target > arr[mid - 1])
                    return getClosest(arr[mid - 1],
                                  arr[mid], target);
                 
                /* Repeat for left half */
                j = mid;             
            }
 
            // If target is greater than mid
            else {
                if (mid < n-1 && target < arr[mid + 1])
                    return getClosest(arr[mid],
                          arr[mid + 1], target);               
                i = mid + 1; // update i
            }
        }
 
        // Only single element left after search
        return arr[mid];
    }
    static void ruffleSort(long[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			long oi=r.nextInt(n), temp=a[i];
			a[i]=a[(int)oi];
			a[(int)oi]=temp;
		}
		Arrays.sort(a);
	}
    static void ruffleSort(int[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n), temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		Arrays.sort(a);
	}
    private int ceilIndex(int input[], int T[], int end, int s){
        int start = 0;
        int middle;
        int len = end;
        while(start <= end){
            middle = (start + end)/2;
            if(middle < len && input[T[middle]] < s && s <= input[T[middle+1]]){
                return middle+1;
            }else if(input[T[middle]] < s){
                start = middle+1;
            }else{
                end = middle-1;
            }
        }
        return -1;
    }
    public static int findIndex(long arr[], long t) 
    { 
 
        // if array is Null 
        if (arr == null) { 
            return -1; 
        } 
 
        // find length of array 
        int len = arr.length; 
        int i = 0; 
 
        // traverse in the array 
        while (i < len) {
            if (arr[i] == t) { 
                return i; 
            } 
            else { 
                i = i + 1; 
            } 
        } 
        return -1; 
    }
 
    static long gcd(long a, long b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
    static long lcm(long a, long b)
    {
        return (a / gcd(a, b)) * b;
    }
 
    public static int[] swap(int a[], int left, int right)
    {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
        return a;
    }
    public static void swap(int max0,int max1)
    {
    	int temp=max0;
    	max0=max1;
    	max1=temp;
    }
 
    public static int[] reverse(int a[], int left, int right)
    {
 
        // Reverse the sub-array
        while (left < right) {
            int temp = a[left];
            a[left++] = a[right];
            a[right--] = temp;
        }
        return a;
    }
 
  
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    
//    *******----segement tree implement---******
    
//    -------------START--------------------------
    
    void buildTree (int[] arr,int[] tree,int start,int end,int treeNode)
    {
    	if(start==end)
    	{
    		tree[treeNode]=arr[start];
    		return;
    	}
    	buildTree(arr,tree,start,end,2*treeNode);
    	buildTree(arr,tree,start,end,2*treeNode+1);
    	tree[treeNode]=tree[treeNode*2]+tree[2*treeNode+1];
    }
    void updateTree(int[] arr,int[] tree,int start,int end,int treeNode,int idx,int value)
    {
    	if(start==end)
    	{
    		arr[idx]=value;
    		tree[treeNode]=value;
    		return;
    	}
    	int mid=(start+end)/2;
    	if(idx>mid)
    	{
    		updateTree(arr,tree,mid+1,end,2*treeNode+1,idx,value);
    	}
    	else
    	{
    		updateTree(arr,tree,start,mid,2*treeNode,idx,value);
    	}
    	tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
    }
    	static int[][] dp;
    	private static long getClosetNumberOfTarget(long[] dataArray, long target) {
    		 
    		// Edge case - Check if array length is zero
    		if (dataArray.length == 0)
    			System.exit(1);
    		// Straight case - If target is smaller or equal to first element in array
    		if (target <= dataArray[0])
    			return dataArray[0];
    		// Straight case - If target is greater or equal to last element in array
    		if (target >= dataArray[dataArray.length - 1])
    			return dataArray[dataArray.length - 1];
     
    		// Start binary search algorithm
    		int start = 0;
    		int end = dataArray.length-1;
    		int mid = 0;
     
    		// Keep dividing array till further division is not possible
    		while (end - start != 1) {
    			// Calculate middle index
    			mid = (start + end) / 2;
    			// Check if middle element is equal to target
    			if (target == dataArray[mid])
    				// If yes return middle element as middle element = target 
    				return dataArray[mid];
    			// Check if target is smaller to middle element. If yes, take first half of array including mid
    			if (target < dataArray[mid]) 
    				end = mid;
    			// Check if target is greater to middle element. If yes, take first half of array including mid
    			if (target > dataArray[mid])
    				start = mid;	
    		}
    		// Now you will have only two numbers in array in which target number will fall
    		return Math.abs(target - dataArray[start]) <= Math.abs(target - dataArray[end]) ? dataArray[start]
    				: dataArray[end];
    	}
    	private static int getClosetNumberOfTarget(int[] dataArray, int target) {
    		 
    		// Edge case - Check if array length is zero
    		if (dataArray.length == 0)
    			System.exit(1);
    		// Straight case - If target is smaller or equal to first element in array
    		if (target <= dataArray[0])
    			return dataArray[0];
    		// Straight case - If target is greater or equal to last element in array
    		if (target >= dataArray[dataArray.length - 1])
    			return dataArray[dataArray.length - 1];
     
    		// Start binary search algorithm
    		int start = 0;
    		int end = dataArray.length - 1;
    		int mid = 0;
     
    		// Keep dividing array till further division is not possible
    		while (start < end) {
    			// Calculate middle index
    			mid = (start + end) / 2;
    			// Check if middle element is equal to target
    			if (target == dataArray[mid])
    				// If yes return middle element as middle element = target
    				return dataArray[mid];
    			// Check if target is smaller to middle element. If yes, take first half of
    			// array including mid
    			if (target < dataArray[mid]) {
    				// If target is greater than previous element of middle element, we have reached the deciding range
    				if (target > dataArray[mid - 1])
    					return Math.abs(target - dataArray[mid]) >= Math.abs(target - dataArray[mid - 1]) ? dataArray[mid-1]
    							: dataArray[mid];
    				end = mid - 1;
    			}
    			// Check if target is greater to middle element. If yes, take first half of
    			// array including mid
    			if (target > dataArray[mid]) {
    				// If target is smaller than next element of middle element, we have reached the deciding range
    				if (target < dataArray[mid + 1])
    					return Math.abs(target - dataArray[mid]) <= Math.abs(target - dataArray[mid + 1]) ? dataArray[mid]
    							: dataArray[mid + 1];
     
    				start = mid + 1;
    			}
    		}
    		// after exiting form loop, middle element will be closer
    		return dataArray[mid];
    	}
    	
//    	disjoint set implementation --start
        static void makeSet(int n)
        {
        	parent=new int[n];
        	rank=new int[n];
        	for(int i=0;i<n;i++)
        	{
        		parent[i]=i;
        		rank[i]=0;
        	}
        	
        }
        static void union(int u,int v)
        {
        	u=findpar(u);
        	v=findpar(v);
        	if(rank[u]<rank[v])parent[u]=v;
        	else if(rank[v]<rank[u])parent[v]=u;
        	else 
        	{
//        		System.out.println(v+" "+parent[v]);
        		parent[v]=u;
//        		System.out.println(v+" "+parent[v]);
        		rank[u]++;
        	}
        }
        
    	private static int findpar(int node)
    	{	
    		if(node==parent[node])return node;
    		return parent[node]=findpar(parent[node]);
    	}
    	static int parent[];
        static int rank[];
    	
//    	*************end
    	static long MOD=(long) 1e+7;
    	class xx implements Comparator<pair> {
    	    // Used for sorting in ascending order of
    	    // roll number
    	    public int compare(pair a, pair b)
    	    {
    	        return (int) (a.x - b.x);
    	    }
    	}
    	private static int lps(int m ,int n,String s1,String s2,int[][]mat)
        {
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(s1.charAt(i-1)==s2.charAt(j-1))mat[i][j]=1+mat[i-1][j-1];
                    else mat[i][j]=Math.max(mat[i-1][j],mat[i][j-1]);
                }
            }
            return mat[m][n];
        }
        static int minimumNumberOfDeletions(String str)
        {
            int n = str.length();
            HashMap<Character,Integer>map=new HashMap<>();
            for(int i=0;i<str.length();i++)
            {
            	map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1);
            }
            String input =str;        
            StringBuilder input1 = new StringBuilder();
            input1.append(input);
            input1.reverse();
            String input2 = input1.toString();
            int x=str.length();
            int y=input2.length();
            int[][] mat=new int[x+1][y+1];
            for(int i=0;i<=x;i++)
            {
                for(int j=0;j<=y;j++)
                {
                    if(i==0)mat[i][j]=0;
                    if(j==0)mat[i][j]=0;
                }
            }
            int len = lps(str.length(),input2.length(),str,input2,mat);
            if(len>=map.size())return -1;
            return n-len;
        }
        static long[] pre=new long[(int) (1e6+1)];
        static void comp()
        {
        	pre[1]=1;
        	pre[2]=2;
        	for(long i=1;i<=1e6;i++)
        	{
        		pre[(int) i]=pre[(int) (i-1)]+i-1;
        	}
        }
        public static void main(String[] args)
        {
        	FastReader s = new FastReader();
	        dp=new int[1001][1001];
	        long tt = s.nextLong();
	        while (tt-->0)
	        {
	        	 long x=s.nextLong();
	        	 long d=s.nextLong();
	            Vector<Long> foo=new Vector<Long>();
	            long cur=x;
	            for(long i = 0 ; i < 4 ; i++) {
	                 long min=i+1;
	                if((cur&1)==1) {
	                    cur+=min;
	                } else {
	                    cur-=min;
	                }
	                foo.add(cur);
	            }
	            long temp = d%4;
	     
	            if(temp==2 || temp==0) {
	                if(temp==0)
	                    temp+=4;
	                System.out.println(foo.get((int) (temp-1)));
	            } else {
	                if(temp==1) {
	                    d--;
	                     long dem = (long) (d/4.0);
	                    if((x&1)==1) {
	                        System.out.println(foo.get((int) (temp-1))+dem*4);
	                    } else {
	                        System.out.println(foo.get((int) (temp-1))-dem*4);
	                    }
	                } else {
	                    d--;
	                    long dem = (long) (d/4.0);
	     
	                    if((x&1)==1) {
	                        System.out.println(foo.get((int) (temp-1))-dem*4);
	                    } else {
	                        System.out.println(foo.get((int) (temp-1))+dem*4);
	                    }
	                }
	            }
	        }
	        	
	        }
        
        static boolean isPalindrome(String str)
        {
            int i = 0, j = str.length() - 1;
            while (i < j) {
                if (str.charAt(i) != str.charAt(j))
                    return false;
                i++;
                j--;
            }
            return true;
        }
        static int count(long a)
        {
        	int cnt=0;
        	for(int i=1;i<=a;i++)
        	{
        		if(gcd(i,a)==1)cnt++;
        	}
        	return cnt;
        }
        static boolean issafe(int i, int j, int r,int c, char ch)
        {
			if (i < 0 || j < 0 || i >= r || j >= c|| ch!= '1')return false;
			else return true;
        }
        static long power(long a, long b)
        {
        	   a %=MOD;
        	    long out = 1;
        	    while (b > 0) {
        	        if((b&1)!=0)out = out * a % MOD;
        	        a = a * a % MOD;
        	        b >>= 1;
        			a*=a;
        	    }
        	    return out;
        }
//        static long power(long x, long y)
//        {
//            long res = 1;     // Initialize result
//          
//            while (y > 0)
//            {
//               
//                // If y is odd, multiply x with result
//                if ((y & 1) != 0)
//                    res = res * x;
//          
//                // y must be even now
//                y = y >> 1; // y = y/2
//                x = x * x;  // Change x to x^2
//            }
//            return res;
//        }

		static boolean check(String str)
        {
            // Compute sum of digits
            int n = str.length();
            int digitSum = 0;
            for (int i=0; i<n; i++)
                digitSum += (str.charAt(i)-'0');
          
            // Check if sum of digits is
            // divisible by 3.
            return (digitSum % 3 == 0);
        }

}
class pair{
	long x,y;
	public pair(long x,long y)
	{
		this.x=x;
		this.y=y;
	}
}



