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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.StringTokenizer;

import static java.lang.Long.compare;


/**
 *
 * 6
 * 7
 * 8
 * 9
 * 10
 * 11
 * 12
 *
 */

public class RandomClass {

    static final Random random = new Random();
    public static class Node implements Comparable<Node>{
        int x;
        int y;

        public Node(int a, int b) {
            x = a;
            y = b;
        }

        @Override
        public int compareTo(Node o) {
            if(this.x > o.x) {
                return +1;
            } else if(this.x == o.x){
                return 0;
            } else {
                return -1;
            }
        }
    }



    public static void main(String args[]) throws Exception {

        FastReader fs = new FastReader();
        StringBuilder sb = new StringBuilder();



        int t = fs.nextInt();

        while(t-->0) {
            int a = fs.nextInt();
            int b = fs.nextInt();

            int initalXor = 0;
            if ( (a-1) % 4 == 0) {
                initalXor = a-1;
            } if ((a-1) % 4 == 3) {
                initalXor = 0;
            } if ((a-1) % 4 == 1) {
                initalXor = 1;
            } if ((a-1) % 4 == 2) {
                initalXor = a;
            }

            int x = initalXor ^ b;
            int count = a;
            if (x == 0) {

            } else {
                if(x == a) {
                    count += 2;
                }
                else{
                    count++;
                }
            }

            sb.append(count+"\n");



        }

        System.out.println(sb);


    }



    static int gcd(int a, int b)
    {
        return (a % b == 0) ?
                Math.abs(b) : gcd(b,a%b);
    }

    static boolean isPossible(int a,
                              int b, int c)
    {
        return (c % gcd(a, b) == 0);
    }


    //Fast Reader
    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;
        }
    }


    static void ruffleSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }

}