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

/**
 * A simple template for competitive programming problems.
 */
public class Solution {
    //InputReader in = new InputReader("input.txt");
    final InputReader in = new InputReader(System.in);

    final PrintWriter out = new PrintWriter(System.out);

    void solve() {
        int t = in.nextInt();
        while(t-->0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int xor = computeXOR(a-1);
            if(xor==b) {
                out.println(a);
            } else if((xor^b)!=a) {
                out.println(a+1);
            } else {
                out.println(a+2);
            }
        }
    }

    static int computeXOR(int n)
    {
        // If n is a multiple of 4
        if (n % 4 == 0)
            return n;

        // If n%4 gives remainder 1
        if (n % 4 == 1)
            return 1;

        // If n%4 gives remainder 2
        if (n % 4 == 2)
            return n + 1;

        // If n%4 gives remainder 3
        return 0;
    }

    public class UnionFind {
        private final int[] component;
        private final int[] size;
        private int componentCount;

        /**
         * Initially each object is only connected to itself.
         */
        public UnionFind(int numObjects) {
            component = new int[numObjects];
            size = new int[numObjects];
            componentCount = numObjects;
            for (int i = 0; i < numObjects; i++) {
                component[i] = i;
                size[i] = 1;
            }
        }

        /**
         * Returns the component ID of the object.
         */
        public int find(int p) {
            if (p < 0 || p >= component.length) throw new IllegalArgumentException("Illegal object ID.");
            int root = p;
            while (component[root] != root)
                root = component[root];
            while (root != component[p]) {
                int next = component[p];
                component[p] = root;
                p = next;
            }
            return root;
        }

        /**
         * Merges the components of the objects.
         */
        public void union(int p, int q) {
            if (p < 0 || p >= component.length) throw new IllegalArgumentException("Illegal object ID.");
            if (q < 0 || q >= component.length) throw new IllegalArgumentException("Illegal object ID.");
            p = find(p);
            q = find(q);
            if (p == q) return;
            componentCount--;
            if (size[p] < size[q]) {
                component[p] = q;
                size[q] += size[p];
            } else {
                component[q] = p;
                size[p] += size[q];
            }
        }

        /**
         * Returns true if the objects are in the same component, false otherwise.
         */
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        /**
         * Returns the size of the component p belong to.
         */
        public int componentSize(int p) {
            return size[find(p)];
        }

        /**
         * Returns the number of components.
         */
        public int count() {
            return componentCount;
        }
    }

    private void shuffle(int[] a) {
        int n = a.length;
        Random random = new Random();
        random.nextInt();
        for (int i = 0; i < n; i++) {
            int change = i + random.nextInt(n - i);
            swap(a, i, change);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int helper = a[i];
        a[i] = a[j];
        a[j] = helper;
    }

    public static void main(final String[] args) throws FileNotFoundException {
        final Solution s = new Solution();
        final Long t1 = System.currentTimeMillis();
        s.solve();
        System.err.println(System.currentTimeMillis() - t1 + " ms");
        s.out.close();
    }

    public Solution() throws FileNotFoundException {
    }

    private static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        Random r = new Random();
        InputReader(final InputStream stream) {
            this.stream = stream;
        }

        InputReader(final String fileName) {
            InputStream stream = null;
            try {
                stream = new FileInputStream(fileName);
            } catch (final FileNotFoundException e) {
                e.printStackTrace();
            }
            this.stream = stream;
        }

        int[] nextArray(final int n) {
            final int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }

        int[][] nextMatrix(final int n, final int m) {
            final int[][] matrix = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            final StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            final StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (final IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        private boolean isSpaceChar(final int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(final int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }

}