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.*;

public class Main {

    static boolean isPowerOfTwo(int n)
    {
        return (int)(Math.ceil((Math.log(n) / Math.log(2))))
                == (int)(Math.floor(((Math.log(n) / Math.log(2)))));
    }




    public static void main(String[] args) {
	// write your code here

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0)
        {
           int a = sc.nextInt();
           int b = sc.nextInt();
           //int ans=0;

           if(a!=1&&isPowerOfTwo(a))
           {
               //System.out.println("power");
               if(a!=2)
               {
                   if(a==b) {
                       System.out.println(a + 2);
                   }
                   else if(b==0)
                   {
                       System.out.println(a);
                   }
                   else
                   {
                       System.out.println(a=1);
                   }
               }
               else {
                   if(b==1)
                   {
                       System.out.println(a);
                   }
                   else
                   {
                       System.out.println(a+1);
                   }
               }
           }
           else
           {
               //System.out.println("not");
               int n = (int)(Math.log(a)/Math.log(2));
               int ans=0;
               if(n>1) {
                   n = (int) Math.pow(2, n);
                   for(int i=n; i<a; i++)
                   {
                       ans=ans^i;
                   }

               }
               else
               {
                   for(int i=0; i<a; i++)
                   {
                       ans=ans^i;
                   }

               }
               if(ans==b)
               {
                   System.out.println(a);
               }
               else if(ans==0 && a==b)
               {
                   System.out.println(a+2);
               }
               else
               {
                   System.out.println(a+1);
               }



           }

        }






    }
}
