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.*;
import java.lang.reflect.Array;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;



public class copy{
    public static int find(int a,int[] parent)
    {
        if(parent[a]==a)
            return a;
        return find(parent[a],parent);
    }

    public static void union(int a,int b,int[] parent, int[] rank)
    {
        int x=find(a,parent);
        int y=find(b,parent);
        if(rank[x]>rank[y])
        {
            parent[y]=x;

        }
        else if(rank[y]>rank[x])
        {
            parent[x]=y;

        }
        else
        {
            parent[y]=x;
            rank[x]++;

        }
    }

    static double answer;

    public static int check(ArrayList<ArrayList<Integer>> edges,int x,int parent,int[] statues,int n)
    {
        ArrayList<Integer> arr=new ArrayList<>();
        for(int i:edges.get(x))
        {
            if(i!=parent)
            {
                arr.add(check(edges,i,x,statues,n));
            }
        }
        int sum=0;
        for(int i=arr.size()-1;i>=0;i--)
        {

            answer+=((long)arr.get(i)*(long)sum*(long)statues[x])/((double)n*(double)(n-1));
            sum+=arr.get(i);
        }
        answer+=((long)sum*(long)statues[x])/((double)n*(double)(n-1));
        //System.out.println(x+" "+sum);
        return 1+sum;
    }

    public static boolean check(int X,int a,int b)
    {
        System.out.println(X);

        if(X==1)
            return true;
        boolean status=false;
        if(X%a==0 && a!=1)
            status=status || check(X/a,a,b);
        if(X-b>=1 && b!=0)
            status=status || check(X-b,a,b);

        return status;


    }

    public static int check(long xor,ArrayList<Long> sum,int low,int N)
    {
        int l=low;
        int r=N-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(sum.get(mid)==xor)
            {
                return mid;
            }
            else
                r=mid-1;
        }

        return 0;
    }

    public static void merge(int l,int mid,int r,cp[] arr,HashMap<Integer,Integer> before)
    {
        int N=mid-l+1,M=r-mid;
        cp[] arr1=new cp[mid-l+1];
        cp[] arr2=new cp[r-mid];
        cp[] arr3=new cp[N+M];
        for(int i=l;i<=mid;i++)
            arr1[i-l]=arr[i];
        for(int i=mid+1;i<=r;i++)
            arr2[i-mid-1]=arr[i];
        int left=0,right=0,k=0;
        while(left<N && right<M)
        {

            if(arr1[left].a<arr2[right].a)
            {
                arr3[k++]=arr1[left++];
            }
            else
            {

                before.put(arr2[right].b,before.getOrDefault(arr2[right].b,0)+N-left);
                count+=N-left;
                arr3[k++]=arr2[right++];
            }
        }

        while(left<N)
        {
            arr3[k++]=arr1[left++];
        }

        while(right<M)
        {
            arr3[k++]=arr2[right++];
        }

        for(int i=l;i<=r;i++)
            arr[i]=arr3[i-l];



    }

    public static void inv(HashMap<Integer,Integer> before,int l,int r,cp[] arr)
    {
        if(l==r)
            return;
        int mid=(l+r)/2;
        inv(before,l,mid,arr);
        inv(before,mid+1,r,arr);
        merge(l,mid,r,arr,before);
    }
    static long count=0;
    public static int check(ArrayList<Long> arr,long X,int low,int N,long mod)
    {
        int l=low;
        int r=N;
        while(l<=r)
        {
            int mid=l+(r-l)/2;
            if(((arr.get(mid)-arr.get(low-1)))/(long)(mid-low+1)<X)
            {
                if(mid+1<=N &&  ((arr.get(mid+1)-arr.get(low-1)))/(long)(mid-low+2)<X)
                    l=mid+1;
                else
                    return mid;
            }
            else
                r=mid-1;
        }

        return -1;
    }

    public static void check(ArrayList<ArrayList<Integer>> arr,int x,int parent,ArrayList<Integer> answer)
    {
        answer.add(x);
        for(int i:arr.get(x))
        {
            if(i!=parent)
            {
                check(arr,i,x,answer);
                answer.add(x);
            }
        }

    }

    static long binpow( long a,  long b,  long m) {
        a %= m;
        long  res = 1;
        while (b > 0) {
            if ((b & 1)==1)
                res = res * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return res;
    }
    public static int check(int N,int a,int b,int c,int[] dp)
    {
        if(dp[N]!=-2)
            return dp[N];
        if(N==0)
            return 0;

        int a1=-1,a2=-1,a3=-1;
        if(N>=a)
            a1=check(N-a,a,b,c,dp);
        if(N>=b)
            a2=check(N-b,a,b,c,dp);
        if(N>=c)
            a3=check(N-c,a,b,c,dp);
        if(a1==-1 && a2==-1 && a3==-1)
            dp[N]=-1;
        else
            dp[N]= 1+Math.max(a1,Math.max(a2,a3));
        return dp[N];
    }



    public static long gcd(long a,long b)
    {
        if(a==0)
            return b;

        return gcd(b%a,a);
    }


    public static int check(ArrayList<Double> arr,double number,int N)
    {
        int l=0;
        int r=N;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(number>=arr.get(mid))
            {
                if(mid+1<=N && arr.get(mid+1)<=number)
                    l=mid+1;
                else
                    return mid;
            }
            else
                r=mid-1;
            //System.out.println("hello");
        }

        return 0;
    }


    //    public static int check(ArrayList<String> arr)
//    {
//        int ans=Integer.MAX_VALUE;
//        ArrayList<Character> copy=new ArrayList<>();
//        for(char ch='a';ch<='z';ch++)
//        {
//            int s1=0;
//            for(String s:arr)
//                if(s.indexOf(ch)!=-1)
//                    ++s1;
//            if(s1>1)
//            {
//                copy.add(ch);
//            }
//
//        }
//        if(copy.size()==0) {
//            for (char ch = 'a'; ch <= 'z'; ch++) {
//                int s1 = 0, s2 = 0;
//                for (String s : arr)
//                    if (s.indexOf(ch) != -1)
//                        s1 += s.length();
//                    else
//                        s2 += s.length();
//
//                //System.out.println(ch+" "+s1+" "+s2);
//                ans = Math.min(ans, Math.abs(s1 - s2));
//
//            }
//        }
//        else
//        {
//            for (char ch:copy) {
//                int s1 = 0, s2 = 0;
//                for (String s : arr)
//                    if (s.indexOf(ch) != -1)
//                        s1 += s.length();
//                    else
//                        s2 += s.length();
//
//                //System.out.println(ch+" "+s1+" "+s2);
//                ans = Math.min(ans, Math.abs(s1 - s2));
//
//            }
//        }
//
//        return ans;
//    }
    static int size;

    public static void swap(int[] arr,int x,int y)
    {
        int temp=arr[x];
        arr[x]=arr[y];
        arr[y]=temp;
    }


    public static void delete(int[] arr)
    {
        swap(arr,0,size-1);
        --size;
        heapify(arr,0);
    }

    public static void heapify(int[] arr,int x)
    {
        int largest=x;
        int left_child=2*x;
        int right_child=2*x+1;

        if(left_child<size && arr[left_child]>arr[largest])
            largest=left_child;
        if(right_child<size && arr[right_child]>arr[largest])
            largest=right_child;

        if(largest!=x)
        {
            swap(arr,x,largest);
            heapify(arr,largest);
        }
    }

    public static int check(ArrayList<Integer> arr,int N,int X)
    {
        int l=0,r=N-1;
        while(l<=r)
        {
            int mid=(l+r)/2;

            if(arr.get(mid)<=X)
            {

                if(mid+1<N && arr.get(mid+1)<=X)
                    l=mid+1;
                else
                    return mid;
            }
            else
                r=mid-1;
        }

        return -1;
    }

    public static cord check(ArrayList<Integer> arr)
    {
        int initial=0,level=0;
        int index=0;
        for(int i=0;i<arr.size();i++)
        {
            if(arr.get(i)<level)
                level+=1;
            else
            {
                initial+=arr.get(i)-level+1;
                level=arr.get(i)+1;
                level+=1;
            }
            //System.out.println(level+" "+i+" "+initial);
        }

        return new cord(initial,initial+arr.size());
    }

    public static boolean vowel(char ch)
    {
        if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')
            return true;
        return false;
    }

    public static void check(int [] values,int N,int index,int max,BufferedWriter output)throws IOException
    {
        if(index>=N)
            return ;
        if(values[index]>max)
        {
            max=values[index];
        }

        output.write(max+" ");
        check(values,N,index+1,max,output);


    }

    public static boolean check(HashMap<Integer,Integer> hp,int days,int N)
    {
        int k=0;
        for(int i:hp.keySet())
            k+=hp.get(i)/days;

        return k>=N;

    }

    public static int search(ArrayList<Integer> arr,int N,int search)
    {
        if(search>arr.get(N-1))
            return N;
        if(search<=arr.get(0))
            return 0;
        int l=0,r=N-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(arr.get(mid)<search)
            {
                if(mid+1<N && search>arr.get(mid+1))
                    l=mid+1;
                else
                    return mid+1;
            }
            else
                r=mid-1;
        }

        return -1;
    }













    public static void main(String[] args)throws IOException
    {
        Reader.init(System.in);
        BufferedWriter output=new BufferedWriter(new OutputStreamWriter(System.out));
        int T=Reader.nextInt();
        int[] xor=new int[300001];
        for(int i=1;i<=300000;i++)
        {
            xor[i]=i^xor[i-1];
        }
        for(int m=1;m<=T;m++)
        {
            int a=Reader.nextInt();
            int b=Reader.nextInt();
//            if(a==1 && b==1)
//            {
//                output.write(3+"\n");
//                continue;
//            }


                if(xor[a-1]==b)
                    output.write(a+"\n");
                else
                {
                    if((xor[a-1]^b)==a)
                        output.write(a+2+"\n");
                    else
                    output.write(a+1+"\n");
                }


            //System.out.println(3^1);





        }





        output.flush();

    }
}

class cord
{
    int x;
    long y;
    cord(int x,long y)
    {
        this.x=x;
        this.y=y;
    }
}

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

    }
}

class sort_cp implements Comparator<cord>
{
    public int compare(cord o1,cord o2)
    {
        if(o1.x<o2.x)
            return -1;
        else if(o2.x<o1.x)
            return 1;
        else
            return 0;
    }
}
class g_node{
    int val;
    long wt;

    g_node(int val, long wt)
    {
        this.val = val;
        this.wt = wt;
    }
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}
