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.math.BigInteger;
import java.util.*;
import java.io.*;

public class B_MEXor_Mixup {
    public static void main (String[] args) {
        FastReader scan = new FastReader();
        int t = scan.nextInt();
        int[] arr = new int[300001];
        for (int i=1; i<=300000; i++) {
            arr[i] = (arr[i-1] ^ i);
        }
        while (t-- > 0) {
            int a = scan.nextInt(), b = scan.nextInt();
            int xor = arr[a-1];
            if (xor == b)
                System.out.println(a);
            else {
                if ((xor ^ b) == a)
                    System.out.println(a+2);
                else
                    System.out.println(a+1);
            }
        }
    }
    public static void inputArray (int[] arr, int n, FastReader scan) {
        for (int i=0; i<n; i++) {
            arr[i] = scan.nextInt();
        }
    }
    public static void printArray (int[] arr) {
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static boolean isPrime (int n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }
    public static int gcd (int a, int b) {
        BigInteger a1 = BigInteger.valueOf(a);
        BigInteger b1 = BigInteger.valueOf(b);
        return a1.gcd(b1).intValue();
    }
    public static int numberOfDigitsInNumber (int n) {
        return (int)Math.floor(Math.log10(n)) + 1;
    }
    public static boolean isPowerOfTwo (int x) {
        return x!=0 && ((x&(x-1)) == 0);   
    }
    public static String toBinaryString (int n) {
        return Integer.toString(n, 2);
        // for other bases change 2 to other bases
    }
    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;
        }
    }
}

// For IO using Files
// public static void main throws IOException
// BufferedReader br = new BufferedReader(new FileReader("input.txt"));
// PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
// String st[]=br.readLine().split(" ");
// int n=Integer.parseInt(st[0]);
// int m=Integer.parseInt(st[1]);
// at the end
// br.close(); pw.close();
// for printing pw.println(), pw.print(), etc...
// for arrays : int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();