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.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
    static int mod=(int)1e9+9;
    static boolean isPerfectSquare(long x)
    {
        if (x >= 0) {
           
            // Find floating point value of
            // square root of x.
            long sr = (long)Math.sqrt(x);
           
            // if product of square root
            // is equal, then
            // return T/F
 
            return ((sr * sr) == x);
        }
        return false;
    }
    public static int xor(int n){
        if(n%4==0)
            return n;
        else if(n%4==1)
            return 1;
        else if(n%4==2)
            return n+1;
        else
            return 0;
    }
    static boolean isSubSequence(String str1, String str2,
                                 int m, int n)
    {
        // Base Cases
        if (m == 0)
            return true;
        if (n == 0)
            return false;
 
        // If last characters of two strings are matching
        if (str1.charAt(m - 1) == str2.charAt(n - 1))
            return isSubSequence(str1, str2, m - 1, n - 1);
 
        // If last characters are not matching
        return isSubSequence(str1, str2, m, n - 1);
    }
       public static void main(String args[]){
            FastScanner in=new FastScanner();
            int test=in.nextInt();
            while(test-->0){
                int a=in.nextInt();
                int b=in.nextInt();
                int xor=xor(a-1);
                if(xor==b)
                    System.out.println(a);
                else if((xor^b)!=a)
                    System.out.println(a+1);
                else
                    System.out.println(a+2);
                    
            }
       }
       public static void reverse(long arr[]){
           long temp[]=arr.clone();
           for(int i=0;i<temp.length;i++){
               arr[i]=temp[temp.length-i-1];
           }
       }
       public static boolean check(ArrayList<Long> list,long mid,long x,long y,long a,long b,long k){
           int index=0;
           long lcm=lcm(a,b);
           long common=mid/lcm;
           long af=mid/a;
           long bf=mid/b;
           
           long cont=0;
           int min=0;
           for(int i=0;i<common;i++){
               cont+=(list.get(index++)/100)*(x+y);
              
           }
           for(int i=0;i<af-common;i++){
               cont+=(list.get(index++)/100)*x;
               
           }
           
           for(int i=0;i<bf-common;i++){
               cont+=(list.get(index++)/100)*y;
           }
           
           if(cont>=k)
               return true;
           else
               return false;
       }
       static String decimalToBinary(int num)
    {
        // Function to print integer to binary using
        // inbuilt toBinaryString method
       return Integer.toBinaryString(num);
    }
       public static boolean check(String s){
           int len=s.length()/2;
           for(int i=0;i<len;i++){
               if(s.charAt(i)!=s.charAt(s.length()-i-1))
                   return false;
           }
           return true;
       }
       static void nPermute(char[] str, int n)
{
    // Sort the string in lexicographically
    // ascending order
    Arrays.sort(str);
  
    // Keep iterating until
    // we reach nth position
    int i = 1;
    do {
        // check for nth iteration
        if (i == n)
            break;
  
        i++;
    } while (next_permutation(str));
  
    // print string after nth iteration
    System.out.println(String.valueOf(str));
}
  
static boolean next_permutation(char[] p)
{
    for (int a = p.length - 2; a >= 0; --a)
        if (p[a] < p[a + 1])
        for (int b = p.length - 1;; --b)
            if (p[b] > p[a]) 
            {
                char t = p[a];
                p[a] = p[b];
                p[b] = t;
                for (++a, b = p.length - 1; a < b; ++a, --b)
                {
                    t = p[a];
                    p[a] = p[b];
                    p[b] = t;
                }
                return true;
            }
    return false;
} 
              
              
              
       public static int dfs(int n,int node,ArrayList<Pair> arr[],boolean visited[],int sum){
          visited[node]=true;
          if(node==n-1)
              return sum;
              
          int max=Integer.MIN_VALUE;
          for(Pair i:arr[node]){
              int ans=0;
              if(!visited[i.x])
                 ans=dfs(n,i.x,arr,visited,sum+i.y);
              
              max=Math.max(ans,max);
          }
           return max;
       }
       public static void factor(long n,HashSet<Long> set){
           for(long i=2;i*i<=n;i++){
               if(n%i==0){
                   set.add(i);
                   while(n%i==0){
                       n=n/i;
                   }
               }
           }
           if(n!=0 && n!=1)
               set.add(n);
       }
       public static int bakchodi(int arr[],int dp[][],int n,int turn,int index){
           if(index>=n)
               return 0;
           
           if(dp[index][turn]!=-1)
               return dp[index][turn];
           
           int ans1=Integer.MAX_VALUE;
           int ans2=Integer.MAX_VALUE;
           if(turn==0){
               if(index<n)
                   ans1=arr[index]+bakchodi(arr,dp,n,1-turn,index+1);
               
               if(index+1<n)
                   ans2=arr[index]+arr[index+1]+bakchodi(arr,dp,n,1-turn,index+2);
           }
           else{
               ans1=bakchodi(arr,dp,n,1-turn,index+1);
               ans2=bakchodi(arr,dp,n,1-turn,index+2);
           }
            return dp[index][turn]=Math.min(ans1,ans2);
       }
       public static int rec1(int arr[],int turn,int index,int n){
           int ans1=0;
           int ans2=0;
           if(index>=n)
               return 0;
           
           if(turn==0){
               if(index<n)
               ans1=arr[index]+rec1(arr,1-turn,index+1,n);
               
               if(index+1<n)
                   ans2=arr[index]+arr[index+1]+rec1(arr,1-turn,index+2,n);
           }
           else{
               ans1=rec1(arr,1-turn,index+1,n);
               ans2=rec1(arr,1-turn,index+2,n);
           }
           return Math.min(ans1,ans2);
       }
       public static int rec(int arr[][],int i,int j,int n){
           int sum=0;
           sum+=arr[i][j];
           
           int max=0;
          for(int k=j+1;k<n;k++)
              max=Math.max(max,rec(arr,1-i,k,n));
          
          sum+=max;
          
          return sum;
       }
      
       public static void rec(int i,int n,int count){
           if(i==n){
               count++;
               return;
           }
           if(i>n)
               return;
           
           rec(i+1,n,count);
           rec(i+2,n,count);
       }
       public static long lcm(long x, long y) {
        return ((x * y) / gcd(x, y));
    }
       public static long gcd(long a,long b){
           if(a==0)
               return b;
           
           return gcd(b%a,a);
       }
       public static int bakloli(char ch[],char c,int k){
           int n=ch.length;
           int k1=0;
           int i=0;
           int j=0;
           int ans=0;
           while(i<n){
               if(j>=n)
                   break;
               while(j<n && (ch[j]==c || k1<k)){
                   if(ch[j]!=c){
                       k1++;
                       
                   }
                   j++;
               }
               ans=Math.max(j-i,ans);
               if(ch[i]!=c)
                   k1--;
               
               i++;
           }
           return ans;
       }
       
       public static long power(long a,long b){
          long ans=1;
          while(b > 0) {
    		if((b&1) == 1) ans = (ans*a) % mod;
    		a = (a*a) % mod;
    		b >>= 1;
    	}
          return ans;
       }
       public static int largestfactor(int n){
          
           for(int i=2;i*i<=n;i++){
               if(n%i==0)
                   return n/i;
           }
           return 1;
       }
      
       public static int bs(int ele,int n,int arr[]){
           int low=0;
           int high=n-1;
           while(low<=high){
               int mid=(low+high)/2;
               if(arr[mid]>=ele){
                   low=mid+1;
               }
               else
                   high=mid-1;
           }
           return low;
       }
       private static int mergeAndCount(long[] arr, int l,
                                     int m, int r)
    {
 
        // Left subarray
        long[] left = Arrays.copyOfRange(arr, l, m + 1);
 
        // Right subarray
        long[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
 
        int i = 0, j = 0, k = l, swaps = 0;
 
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j])
                arr[k++] = left[i++];
            else {
                arr[k++] = right[j++];
                swaps += (m + 1) - (l + i);
            }
        }
        while (i < left.length)
            arr[k++] = left[i++];
        while (j < right.length)
            arr[k++] = right[j++];
        return swaps;
    }
 
    // Merge sort function
    private static int mergeSortAndCount(long[] arr, int l,
                                         int r)
    {
 
        // Keeps track of the inversion count at a
        // particular node of the recursion tree
        int count = 0;
 
        if (l < r) {
            int m = (l + r) / 2;
 
            // Total inversion count = left subarray count
            // + right subarray count + merge count
 
            // Left subarray count
            count += mergeSortAndCount(arr, l, m);
 
            // Right subarray count
            count += mergeSortAndCount(arr, m + 1, r);
 
            // Merge count
            count += mergeAndCount(arr, l, m, r);
        }
 
        return count;
    }
}
class FastScanner {
		java.io.BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
 
		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		int[] readArray(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());
		}
	}
class Pair{
    int x;
    int y;
    Pair(int x,int y){
        this.x=x;
        this.y=y;
    }
}
class Sorting implements Comparator<Pair>{
        public int compare(Pair p1, Pair p2){
            if(p2.x==p1.x){
                return p1.y-p2.y;
            }
            return p1.x - p2.x;
        }
    }