Alice gave Bob two integers a and b (a > 0 and b ≥ 0). Being a curious boy, Bob wrote down an array of non-negative integers with \operatorname{MEX} value of all elements equal to a and \operatorname{XOR} value of all elements equal to b.

What is the shortest possible length of the array Bob wrote?

Recall that the \operatorname{MEX} (Minimum EXcluded) of an array is the minimum non-negative integer that does not belong to the array and the \operatorname{XOR} of an array is the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all the elements of the array.

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 5 ⋅ 10^4) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers a and b (1 ≤ a ≤ 3 ⋅ 10^5; 0 ≤ b ≤ 3 ⋅ 10^5) — the \operatorname{MEX} and \operatorname{XOR} of the array, respectively.

Output

For each test case, output one (positive) integer — the length of the shortest array with \operatorname{MEX} a and \operatorname{XOR} b. We can show that such an array always exists.

Example

Input


5
1 1
2 1
2 0
1 10000
2 10000


Output


3
2
3
2
3

Note

In the first test case, one of the shortest arrays with \operatorname{MEX} 1 and \operatorname{XOR} 1 is [0, 2020, 2021].

In the second test case, one of the shortest arrays with \operatorname{MEX} 2 and \operatorname{XOR} 1 is [0, 1].

It can be shown that these arrays are the shortest arrays possible.
import java.util.*;


import java.lang.*;
import java.io.*;

public class Template {
	
	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;
  }
  
}
    static String kthLargestNumber(String[] nums, int k) {
        Arrays.sort(nums, new Comparator<String>(){
            @Override
            public int compare(String a, String b){
                if(a.length() != b.length()) return a.length() - b.length();
                return a.compareTo(b);
            }
        });
        return nums[nums.length-k];
    }

	static void printMatrix(int mat[][])
	{
		for(int i=0;i<mat.length;i++)
		{
			for(int j=0;j<mat[0].length;j++)
			{
				System.out.print(mat[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	static void printArray(int a[])
	{
		for(int i=0;i<a.length;i++)	
		{
			System.out.print(a[i]+" ");
		}
		System.out.println();
		
	}

//	    public static void main(String args[])
//	    {
//	    	FastReader sc = new FastReader();
//	    	//solve();
//	    	//Scanner sc = new Scanner(System.in)
//	       int testcases = sc.nextInt();  // nTest is the number of treasure hunts.
//	      
////	    	int testcases = 3;
//	        while(testcases-- > 0)
//	        {
//	        	String s = sc.next();
//	        	solve(s);
//	        	
//	        }
//	    
//	    }
	


	public static void main(String[] args) {
	
		System.out.println(0^2020);
		FastReader sc=new FastReader();
		//PrintWriter out = new PrintWriter(System.out);
		int T=sc.nextInt();

		outer:for (int tt=0; tt<T; tt++) {			
			
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			int ans = a;
			int xor = 0;
			for(int i=1;i<a;i++)
			{
				xor = xor ^ i;
			}
			
			if(xor == b)
			{
				System.out.println(ans);
				continue;
			}
			if((a ^ xor) == b)
			{
				System.out.println(ans+2);
				continue;
			}
			System.out.println(ans+1);
			
			
			
		}
	
	}
}


