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

public class Solution
{
    static class Reader {
		BufferedReader br;
		StringTokenizer st;
 
		public Reader() {
			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[] nextArr(int n)
		{
		    int a[]=new int[n];
		    for (int i=0;i<n;i++)a[i]=nextInt();
		    return a;
		}
		
		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 class Ele implements Comparable<Ele> 
    {  
        public int x,y;  
        Ele(int x1,int y1) 
        {  
            x=x1;y=y1; 
        }  
        public int compareTo(Ele ob) {  
        if(ob.x!=x)return x-ob.x;
        return this.y-ob.y;  
        }   
        public String toString()
        {
        	return "["+x+","+y+"]";
        }
    }
	void disp(PrintWriter o,boolean b)
    {
        if (b) o.println("Yes");
        else o.println("No");
    }
    void disp(PrintWriter o,int ...a)
    {
        o.println(Arrays.toString(a));
    }
    void disp(PrintWriter o,long ...a)
    {
        o.println(Arrays.toString(a));
    }
    int dp[][];

	public static void main(String[] args) throws IOException 
	{
		Reader sc=new Reader();Solution G=new Solution();
		PrintWriter o = new PrintWriter(System.out);
		int t=1;t=sc.nextInt();
		int mod=(int)1e9+7;
		int x,x0,x1,x2;int y,y0,y1,y2;int s,s0,s1,s2;
		int n,m;int a[],b[],in[],in1[];
		long k,l;boolean v[],b1,b2;String ss;char c1[],c2[];
		//long l;long a[]; 
		ArrayList<ArrayList<Integer>> ll=new ArrayList<>();
		ArrayList<Integer> a1=new ArrayList<>();
		ArrayList<Integer> a2=new ArrayList<>();
		PriorityQueue<Integer> pq1=new PriorityQueue<>();
		PriorityQueue<Integer> pq2=new PriorityQueue<>(Collections.reverseOrder());
		ArrayDeque<Integer> dq=new ArrayDeque<>();
		TreeSet<Integer> h0=new TreeSet<>();
		TreeSet<Integer> h1=new TreeSet<>();
		TreeMap<Integer,Integer> h=new TreeMap<>();
		try{
		    a=new int[(int)1e6];
		    for (int i=1;i<1e4;i++)
		    {
		        a[i]=a[i-1]^i;
		    }
		while (t-->0)
		{
		    n=sc.nextInt();m=sc.nextInt();
		    
		    x=a[n-1];
		    if (x==m)o.println(n);
		    else if (a[n]==m)o.println(n+2);
		    else o.println(n+1);
		    
		    //c1=sc.next().toCharArray();
		    //m=0;
		    //for (int i:c1)m=Math.max(i-'0',m);
		    //o.println(l);
		    //o.println((x>m)?"No":"Yes");
		    //o.println();
		    //o.println();
		    //o.println(h);
		    //o.println(x2);
		    //o.println();
		    h0.clear();
		    ll.clear();
		    //a1.clear();
		    a2.clear();h1.clear();h.clear();pq1.clear();pq2.clear();
		}
		}
		catch (Throwable e)
		{
		    e.printStackTrace();
		}
		//o.println("HI");
		
        o.flush();
        o.close();
	}
} 