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 static java.lang.Math.*;
import static java.lang.System.out;
import static java.lang.System.setProperty;

import java.util.*;
import java.io.*;
import java.math.*;
public class A {
        public static void main(String hi[]) throws Exception {
            FastScanner s = new FastScanner();
        int T = s.nextInt();
//            int T = 1;
            while (T-- > 0) {
                int a = s.nextInt();
                int b = s.nextInt();
                int ans=0;
                int x=0;
                for(int i=1;a>1 && i*i<=a;i++){
                    x = x^i;
                }
                if(x==b) ans=a;
                else if(a==b){
                    if(x==0)ans = a+2;
                    else ans = a+1;
                }
                else if(x==0)ans=a+1;
                else ans= a+1;
                out.println(ans);
            }
        }
        //input shenanigans
      /*
         Random stuff to try when stuck:
            -in case for TLE in optimised solution use stringBuilder
            -for combo/probability problems, expand the given form we're interested in
            -make everything the same then build an answer (constructive, make everything 0 then do something)
            -something appears in parts of 2 --> model as graph
            -assume a greedy then try to show why it works
            -find way to simplify into one variable if multiple exist
            -treat it like fmc (note any passing thoughts/algo that could be used so you can revisit them)
            -find lower and upper bounds on answer
            -figure out what ur trying to find and isolate it
            -see what observations you have and come up with more continuations
            -work backwards (in constructive, go from the goal to the start)
            -turn into prefix/suffix sum argument (often works if problem revolves around adjacent array elements)
            -instead of solving for answer, try solving for complement (ex, find n-(min) instead of max)
            -draw something
            -simulate a process
            -dont implement something unless if ur fairly confident its correct
            -after 3 bad submissions move on to next problem if applicable
            -do something instead of nothing and stay organized
            -write stuff down
         Random stuff to check when wa:
            -if code is way too long/cancer then reassess
            -switched N/M
            -int overflow
            -switched variables
            -wrong MOD
            -hardcoded edge case incorrectly
         Random stuff to check when tle:
            -continue instead of break
            -condition in for/while loop bad
         Random stuff to check when rte:
            -switched N/M
            -long to int/int overflow
            -division by 0
            -edge case for empty list/data structure/N=1
      */
        public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception {
            int[] arr = new int[N];
            st = new StringTokenizer(infile.readLine());
            for (int i = 0; i < N; i++)
                arr[i] = Integer.parseInt(st.nextToken());
            return arr;
        }

        public static long[] readArr2(int N, BufferedReader infile, StringTokenizer st) throws Exception {
            long[] arr = new long[N];
            st = new StringTokenizer(infile.readLine());
            for (int i = 0; i < N; i++)
                arr[i] = Long.parseLong(st.nextToken());
            return arr;
        }

        public static void print(int[] arr) {
            //for debugging only
            for (int x : arr)
                out.print(x + " ");
            out.println();
        }

        static long gcd(long a, long b) throws IOException {
            return (b == 0) ? a : gcd(b, a % b);
        }

        static int gcd(int a, int b) throws IOException {
            return (b == 0) ? a : gcd(b, a % b);
        }

        public static boolean isPrime(long n) {
            if (n < 2) return false;
            if (n == 2 || n == 3) return true;
            if (n % 2 == 0 || n % 3 == 0) return false;
            long sqrtN = (long) Math.sqrt(n) + 1;
            for (long i = 6L; i <= sqrtN; i += 6) {
                if (n % (i - 1) == 0 || n % (i + 1) == 0) return false;
            }
            return true;
        }

        static void sortr(int[] a) {
            ArrayList<Integer> l = new ArrayList<>();
            for (int i : a) l.add(i);
            Collections.sort(l, Collections.reverseOrder());
            for (int i = 0; i < a.length; i++) a[i] = l.get(i);
        }

        static void sort(int[] a) {
            ArrayList<Integer> l = new ArrayList<>();
            for (int i : a) l.add(i);
            Collections.sort(l);
            for (int i = 0; i < a.length; i++) a[i] = l.get(i);
        }

        static void sort(long[] a) {
            ArrayList<Long> l = new ArrayList<>();
            for (long i : a) l.add(i);
            Collections.sort(l);
            for (int i = 0; i < a.length; i++) a[i] = l.get(i);
        }

        public static long power(long x, long y, long p) {
            //0^0 = 1
            long res = 1L;
            x = x % p;
            while (y > 0) {
                if ((y & 1) == 1)
                    res = (res * x) % p;
                y >>= 1;
                x = (x * x) % p;
            }
            return res;
        }

        static class FastScanner {
            //I don't understand how this works lmao
            private int BS = 1 << 16;
            private char NC = (char) 0;
            private byte[] buf = new byte[BS];
            private int bId = 0, size = 0;
            private char c = NC;
            private double cnt = 1;
            private BufferedInputStream in;

            public FastScanner() {
                in = new BufferedInputStream(System.in, BS);
            }

            public FastScanner(String s) {
                try {
                    in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
                } catch (Exception e) {
                    in = new BufferedInputStream(System.in, BS);
                }
            }

            private char getChar() {
                while (bId == size) {
                    try {
                        size = in.read(buf);
                    } catch (Exception e) {
                        return NC;
                    }
                    if (size == -1) return NC;
                    bId = 0;
                }
                return (char) buf[bId++];
            }

            public int nextInt() {
                return (int) nextLong();
            }

            public int[] nextInts(int N) {
                int[] res = new int[N];
                for (int i = 0; i < N; i++) {
                    res[i] = (int) nextLong();
                }
                return res;
            }

            public long[] nextLongs(int N) {
                long[] res = new long[N];
                for (int i = 0; i < N; i++) {
                    res[i] = nextLong();
                }
                return res;
            }

            public long nextLong() {
                cnt = 1;
                boolean neg = false;
                if (c == NC) c = getChar();
                for (; (c < '0' || c > '9'); c = getChar()) {
                    if (c == '-') neg = true;
                }
                long res = 0;
                for (; c >= '0' && c <= '9'; c = getChar()) {
                    res = (res << 3) + (res << 1) + c - '0';
                    cnt *= 10;
                }
                return neg ? -res : res;
            }

            public double nextDouble() {
                double cur = nextLong();
                return c != '.' ? cur : cur + nextLong() / cnt;
            }

            public double[] nextDoubles(int N) {
                double[] res = new double[N];
                for (int i = 0; i < N; i++) {
                    res[i] = nextDouble();
                }
                return res;
            }

            public String next() {
                StringBuilder res = new StringBuilder();
                while (c <= 32) c = getChar();
                while (c > 32) {
                    res.append(c);
                    c = getChar();
                }
                return res.toString();
            }

            public String nextLine() {
                StringBuilder res = new StringBuilder();
                while (c <= 32) c = getChar();
                while (c != '\n') {
                    res.append(c);
                    c = getChar();
                }
                return res.toString();
            }

            public boolean hasNext() {
                if (c > 32) return true;
                while (true) {
                    c = getChar();
                    if (c == NC) return false;
                    else if (c > 32) return true;
                }
            }
        }
    }
