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 Java;
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;
import java.util.Map.Entry;

public class Main {
	static int dirx[]= {-1,1,0,0};static int diry[]= {0,0,-1,1};
	static final PrintWriter out = new PrintWriter(System.out, true);
    static final FastScanner sc = new FastScanner();
	public static void main(String[] args)  {
		
		int t=sc.nextInt();
		while(t-->0) {
			long x=sc.nextLong();long y=sc.nextLong(),ans=0;
			 if (y % 4 == 0)
			    {
			        ans = 0;
			    }
			    else if (y % 4 == 1)
			    {
			        ans = y;
			    }
			    else if (y % 4 == 2)
			    {
			        ans = -1;
			    }
			    else
			    {
			        ans = -(y + 1);
			    }
			 
			    if (x % 2 == 0)
			    {
			        ans = -ans;
			    }
			    ans+=x;
			    out.println(ans);
		}
		
		
		out.close();
	}
	static void permute(String str, int l, int r,HashSet<String>h)
    {
        if (l == r)
            h.add(str);
        else
        {
            for (int i = l; i <= r; i++)
            {
                str = swap(str,l,i);
                permute(str, l+1, r,h);
                str = swap(str,l,i);
            }
        }
    }
 
    /**
    * Swap Characters at position
    * @param a string value
    * @param i position 1
    * @param j position 2
    * @return swapped string
    */
    public static String swap(String a, int i, int j)
    {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i] ;
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
static long Cr(int n, int r,int mod,long fac[],long inv[]) {
    	if(n<r) return 0L;
		return fac[n]*(inv[r]*inv[n - r]%mod)%mod;
 
//    	long fac[]=new long[100000];
//    	long inv[]=new long[100000];
//    	fac[0]=fac[1]=1;
//    	fac[i]=modmul(fac[i-1],i,m);
//		inv[i] =modpow(fac[i], m - 2,m);
//    	long ans = 1;
//	    ans *= (Cr(n-x,more,m,fac,inv)*fac[more])%m;
//	    ans %= m;
}
	static boolean [] sieveOfEratosthenes(int n){
	    boolean prime[] = new boolean[n + 1];
	    for (int i = 0; i <= n; i++)
	        prime[i] = true;
	
	    for (int p = 2; p * p <= n; p++)
	    {
	        if (prime[p] == true)
	        {
	            for (int i = p * p; i <= n; i += p)
	                prime[i] = false;
	        }
	    }
	    prime[1]=prime[0]=false;
	    return prime;
	}
	static void divisors(int n,ArrayList a[]) {
		for(int i=1;i<=n;i++) {
			for(int j=i;j<=n;j+=i) {
				a[j].add(i);
			}
		}
	}
	 static long modDivide(long a, long b, int m)
	  {
	      a = a % m;
	      long inv = modInverse(b, m);
	      if (inv == -1) return -1;
	      else
	      {
	        long c = (inv * a) % m ;
	        return c;
	      }
	  }
	  static long modInverse(long a, int m){
	        long g = gcd(a, m);
	        if (g != 1) return -1;
	        else
	        {
	        	return modpow(a,m-2,m);
	        }
	    }
	  public static double logx(long m,int x){
	        double result = (double)(Math.log(m) / Math.log(x));
	  
	        return result;
	    }
	     static double setPrecision(double ans,int k){
	    	 double y=Math.pow(10,k);
	    	 return Math.round(ans*y)/y;
	     }
	  public static double log2(double m)
	    {
	        double result = (double)(Math.log(m) / Math.log(2));
	  
	        return result;
	    }
	  static int countDivisors(int n)
	    { int ans=0;
	        for (int i=1; i<=Math.sqrt(n); i++)
	        {
	            if (n%i==0)
	            {
	                if (n/i == i) ans++;
//	                    System.out.print(" "+ i);
	      
	                else ans+=2;
//	                    System.out.print(i+" " + n/i + " " );
	            }
	        }
			return ans;
	    }
	  static ArrayList<Integer> pyyy = new ArrayList<Integer>();
		static void sieveppp(int MAX) 
		{ 
		    int[] isPrime=new int[MAX+1]; 
		  
		    for (int i = 2; i<= MAX; i++) 
		    { 
		        if (isPrime[i] == 0) 
		        { 
		        	pyyy.add(i); 
		            for (int j = 2; i * j<= MAX; j++) 
		                isPrime[i * j]= 1; 
		        } 
		    } 
		} 
		 static int phi(int n) { 
			 ///   call sieveppp(n) in main fn
		      int res = n; 
		      for (int i=0; pyyy.get(i)*pyyy.get(i) <= n; i++) 
		      { 
		          if (n % pyyy.get(i)== 0) 
		          { 
		              res -= (res / pyyy.get(i)); 
		              while (n % pyyy.get(i)== 0) 
		              n /= pyyy.get(i); 
		          } 
		      } 
		      if (n > 1) 
		      res -= (res / n); 
		    
		      return res; 
		  } 
	public static void sort(long[] arr){//because Arrays.sort() uses quicksort which is in worst O(n^2)
		//Collections.sort() uses merge sort
		ArrayList<Long> ttttt = new ArrayList<Long>();
		for(long y: arr)ttttt.add(y);Collections.sort(ttttt);
		for(int i=0; i < arr.length; i++)arr[i] = ttttt.get(i);
	}
	public static void sort(int[] arr){//because Arrays.sort() uses quicksort which is dumb
		//Collections.sort() uses merge sort
		ArrayList<Integer> ttttt = new ArrayList<>();
		for(int y: arr)ttttt.add(y);Collections.sort(ttttt);
		for(int i=0; i < arr.length; i++)arr[i] = ttttt.get(i);
	}
	static boolean check(double[] a,double m,int n,int k) {
		int ans=0;
		for(int i=0;i<n;i++) {
			ans+=(Math.floor(a[i]/m));
			if(ans>=k) return true;
		}
		return ans>=k;
	}
	     static boolean isKthBitSet(long n, int k) { 
			if ((n & (1 << (k - 1))) > 0) 
			return true;
			else
			return false;
			
		 } 
	     static long modpow(long a,long b,int m) {
	    	 if(b==0) return 1;
	    	 if(b==1) return a;
	    	 long ans=0;
	    	 long t=modpow(a,b/2,m);
	    	 ans=modmul(t,t,m);
	    	 if(b%2!=0) ans=modmul(a,ans,m);
	    	 return ans;
	     }
		static long modmul(long a,long b,int m) {
			return mod(mod(a,m)*mod(b,m),m);
		}
		static long mod(long x,int m) {
			return ((x%m)+m)%m;
		}
		 static int octaltodecimal(int deciNum)
		    {
		        int octalNum = 0, countval = 1;
		        int dNo = deciNum;
		        while (deciNum != 0) {
		 
		            // decimals remainder is calculated
		            int remainder = deciNum % 8;
		 
		            // storing the octalvalue
		            octalNum += remainder * countval;
		 
		            // storing exponential value
		            countval = countval * 10;
		            deciNum /= 8;
		        }
		       return octalNum;
		    }
		
	  public static int floorSqrt(int x) 
	    { 
	        // Base Cases 
	        if (x == 0 || x == 1) 
	            return x; 
	  
	        // Do Binary Search for floor(sqrt(x)) 
	        int start = 1, end = x, ans=0; 
	        while (start <= end) 
	        { 
	            int mid = (start + end) / 2; 
	  
	            // If x is a perfect square 
	            if (mid*mid == x) 
	                return mid; 
	  
	            // Since we need floor, we update answer when mid*mid is 
	            // smaller than x, and move closer to sqrt(x) 
	            if (mid*mid < x) 
	            { 
	                start = mid + 1; 
	                ans = mid; 
	            } 
	            else   // If mid*mid is greater than x 
	                end = mid-1; 
	        } 
	        return ans; 
	    } 
		static int div(int n,int b) {
			int g=-1;
			for(int i=2;i<=Math.sqrt(n);i++) {
				if(n%i==0&&i!=b) {
					g=i;
					break;
				}
			}
			return g;
		}
	 
	  
	  public static long gcd(long a, long a2) 
	    { 
	        if (a == 0) 
	            return a2; 
	          
	        return gcd(a2%a, a); 
	    } 
	   public static long lcm(long a, long b)  
	  {  
	     return (a*b)/gcd(a, b);  
	  }  
       public static boolean isPrime(int n) {
           if (n <= 1) {
               return false;
           }
           if (n == 2) {
               return true;
           }
           if (n % 2 == 0) {
               return false;
           }
           for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
               if (n % i == 0) {
                   return false;
               }
           }
           return true;
       }
	      
       static class FastScanner {
           BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
           StringTokenizer strToken = new StringTokenizer("");
           String next() {
        	   while (!strToken.hasMoreTokens()) {
        		   try {
        			   strToken = new StringTokenizer(input.readLine()); 
        		   }  catch (IOException e) { 
        			    e.printStackTrace();
        			  } 
        	   } return strToken.nextToken(); 
        	}
           String nextLine() {
        	   String strrrrr = ""; try {
        		   strrrrr = input.readLine(); 
        	   } catch (IOException e) {
        			   e.printStackTrace(); 
        		}
        	   return strrrrr; 
           }
           int nextInt() {
        	   return Integer.parseInt(next()); 
        	}
           int[] nextIntArray(int n) {
        	   int[] a = new int[n]; 
        	   for (int i = 0; i < n; i++) a[i] = nextInt(); 
        	   return a; 
           }
           long nextLong() {
        	   return Long.parseLong(next()); 
        	}
           long[] nextLongArray(int n) {
        	   long[] a = new long[n];
        	   for (int i = 0; i < n; i++) a[i] = nextLong(); 
        	   return a; 
        	}
           double nextDouble() {
        	   return Double.parseDouble(next()); 
           }
       }
}
class DisjointSet {
    
    private int[] parent;
    private int[] rank;
    
    public DisjointSet(int n) {
        if (n < 0) throw new IllegalArgumentException();
        parent = new int[n];
        for(int i=0;i<n;i++) parent[i]=i;
        rank = new int[n];
    }
    
    public int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // Path compression by halving.
    }
    
    // Return false if x, y are connected.
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;
        
        // Make root of smaller rank point to root of larger rank.
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootX] = rootY;
            rank[rootY]++;
        }
        
        return true;
    }
}


class Pair{
  int value;
  int distance;
  Pair(int value,int distance){
      this.value=value;
      this.distance=distance;
  }
  
}
class sortbydistance implements Comparator<Pair>{

	@Override
	public int compare(Pair o1, Pair o2) {
		return o1.distance-o2.distance;
	}
	
}
class Solution
{
  static int[] dijkstra(int n, ArrayList<ArrayList<ArrayList<Integer>>> adj,ArrayList<Integer>ans)
  {
  	 PriorityQueue<Pair>set=new PriorityQueue<>(new sortbydistance());
      int dis[]=new int[n];
      Arrays.fill(dis,Integer.MAX_VALUE);
      dis[0]=0;
      while(set.isEmpty()==false) {
      	Pair p=set.poll();
      	int u=p.value;
      	for(int i=0;i<adj.get(u).size();i++) {
      		int v=adj.get(u).get(i).get(0);
      		int wt=adj.get(u).get(i).get(1);
      		if(dis[v]>dis[u]+wt) {
      			if(dis[v]!=Integer.MAX_VALUE) {
      				set.remove(new Pair(dis[v],v));
      			}
      			dis[v]=dis[u]+wt;
      			ans.add(v);
      			set.add(new Pair(v,dis[v]));
      		}
      		
      	}
      }
      
      
      return dis;
  }
}


/*    Points- 
 * 
 *    1) when need max and min both use treeset if duplicates are there then use treeset<int []> and add a[1] as unique
 *    number but imp is to make new TreeSet<>((x,y)->(x[0]==y[0])?(x[1]-y[1]):(x[0]-y[0]))  in this x[0]==y[0] cond.
 *    is important 
 *    
 *    2) n!/2 is not fac[n]/2 it is modmul(fac[n],inv[2],m)
 *    
 *    3) if sorting can think of TreeSet also bro or want max and min use tree set as it has last and first function
 *    
 *    4) if dp is not optimisable then think of changing the defination of dp states
*/

class pairs{
	int a,b;
	pairs(int a,int b){
		this.a=a;this.b=b;
	}
}
