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 javax.swing.*;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    import java.util.*;
    public class Main extends PrintWriter {
        static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));Main () { super(System.out); }public static void main(String[] args) throws IOException{ Main  d1=new Main   ();d1.main();d1.flush(); }

        void main() throws IOException {
            StringBuilder sb = new StringBuilder();
            int t = 1;
            t = i(s()[0]);
            int[] xor = new int[3 * 100005];
            for(int i = 1; i < 300000; i++){
                xor[i] = i * xor[i - 1];
            }
            while(t-- > 0) {
                 String[] s = s();
                 int a = i(s[0]); int b= i(s[1]);
                 int xorr = xor[a - 1];
                 int ans = a;
                 if(xorr != b){
                     int val = xorr ^ b;
                     if(val == a) ans += 2;
                     else ans += 1;
                 }
                 sb.append(ans + "\n");
            }
              System.out.println(sb);
        }
        long[] st;//new long[4*n];
        long query(int i,int s,int e,int qs,int qe){
            if(qs>e||qe<s) return 0;
            if(s>=qs&&e<=qe) return st[i];
            int mid=(s+e)/2;
            long l=query(2*i,s,mid,qs,qe);
            long r=query(2*i+1,mid+1,e,qs,qe);
            return (l + r);
        }
        void pointupdate(int i, int s,int e,int qi,int  a){
            if(s == e){
                st[i] += a;return;
            }
            int mid = (s + e) / 2;
            if(qi <= mid) pointupdate(2 * i, s, mid, qi, a);
            else pointupdate(2 * (i) + 1,mid + 1, e, qi, a);
            st[i]=(st[2*i] + st[2*i+1]);
        }
        static String[] s() throws IOException { return s.readLine().trim().split("\\s+"); }
        static int i(String ss) {return Integer.parseInt(ss); }
        static long l(String ss) {return Long.parseLong(ss); }
        public void arr(long[] a,int n) throws IOException {String[] s2=s();for(int i=0;i<n;i++){ a[i]=l(s2[i]); }}
        public void arri(int[] a,int n) throws IOException {String[] s2=s();for(int i=0;i<n;i++){ a[i]=(i(s2[i])); }}

    }class Pair{
           int max, m;
           public Pair(long a, long b){
               max = (int)a ; m = (int)b;
        }
    }


