description: 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.
solution: 
  
  import java.io.DataInputStream;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.util.*;
  
  public class Main {
  
      static class Reader {
          final private int BUFFER_SIZE = 1 << 16;
          private DataInputStream din;
  
          private byte[] buffer;
          private int bufferPointer, bytesRead;
  
          public Reader() {
              din = new DataInputStream(System.in);
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
  
          public Reader(String file_name) throws IOException {
              din = new DataInputStream(
                      new FileInputStream(file_name));
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
  
          public String readLine() throws IOException {
              byte[] buf = new byte[64]; // line length
              int cnt = 0, c;
              while ((c = read()) != -1) {
                  if (c == '\n') {
                      if (cnt != 0) {
                          break;
                      } else {
                          continue;
                      }
                  }
                  buf[cnt++] = (byte) c;
              }
              return new String(buf, 0, cnt);
          }
  
          public int nextInt() throws IOException {
              int ret = 0;
              byte c = read();
              while (c <= ' ') {
                  c = read();
              }
              boolean neg = (c == '-');
              if (neg)
                  c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
  
              if (neg)
                  return -ret;
              return ret;
          }
  
          public long nextLong() throws IOException {
              long ret = 0;
              byte c = read();
              while (c <= ' ')
                  c = read();
              boolean neg = (c == '-');
              if (neg)
                  c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg)
                  return -ret;
              return ret;
          }
  
          public double nextDouble() throws IOException {
              double ret = 0, div = 1;
              byte c = read();
              while (c <= ' ')
                  c = read();
              boolean neg = (c == '-');
              if (neg)
                  c = read();
  
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
  
              if (c == '.') {
                  while ((c = read()) >= '0' && c <= '9') {
                      ret += (c - '0') / (div *= 10);
                  }
              }
  
              if (neg)
                  return -ret;
              return ret;
          }
  
          private void fillBuffer() throws IOException {
              bytesRead = din.read(buffer, bufferPointer = 0,
                      BUFFER_SIZE);
              if (bytesRead == -1)
                  buffer[0] = -1;
          }
  
          private byte read() throws IOException {
              if (bufferPointer == bytesRead)
                  fillBuffer();
              return buffer[bufferPointer++];
          }
  
          public void close() throws IOException {
              if (din == null)
                  return;
              din.close();
          }
      }
  //
  //
  
   
  //
  //       if(flag==0){
  //
  //           StringBuilder stringBuilder = new StringBuilder(s.substring(0,s.length()-1));
  //           double ans= 0.0;
  //           for(int j=1;j<10;j++){
  //               StringBuilder str=new StringBuilder(stringBuilder);
  //               str.append(j);
  //
  //               ans=(double)((double)ans+(double)maxx(1,str.toString(),t,k));
  //           }
  //           return ans;
  //       }
  //       else if(flag==1){
  //
  //           StringBuilder stringBuilder = new StringBuilder(t.substring(0,t.length()-1));
  //           double ans= 0.0;
  //           for(int j=1;j<10;j++){
  //               StringBuilder str=new StringBuilder(stringBuilder);
  //               str.append(j);
  //               ans=(double)((double)ans+(double)maxx(2,s,str.toString(),k));
  //           }
  //           return ans;
  //
  //       }
  //       else{
  //           long[] count=new long[10];
  //           long taka=0;
  //           long[] tot=new long[10];
  //
  //           for(int j=0;j<s.length();j++){
  //               int a=Integer.parseInt(String.valueOf(s.charAt(j)));
  //               count[a]++;
  //               tot[a]++;
  //           }
  //           for(int j=1;j<10;j++){
  //               taka=(long)((long)taka+(long)((long)Math.pow(10,count[j])*(long)j));
  //           }
  //           long aoki=0;
  //           count=new long[10];
  //           for(int j=0;j<t.length();j++){
  //               int a=Integer.parseInt(String.valueOf(t.charAt(j)));
  //               count[a]++;
  //               tot[a]++;
  //           }
  //           for(int j=1;j<10;j++){
  //               aoki=(long)((long)aoki+(long)((long)Math.pow(10,count[j])*(long)j));
  //           }
  //           if(aoki>=taka){
  //               return 0;
  //           }else{
  //               if(t.charAt(t.length()-1)==s.charAt(s.length()-1)){
  //                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)2;
  //                   return (double)((double)((double)(kk)*(double)(kk-(double)1))/(double)((double)1*((double)9*(double)k-(double)8)*(double)((double)9*(double)k-(double)9)));
  //
  //               }else{
  //                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)1;
  //                   double kk2=(double)k-(double)tot[Integer.parseInt(String.valueOf(s.charAt(s.length()-1)))]+(double)1;
  //                   return (double)(((double)((double)1*(double)kk)*(double)(kk2))/(double)((double)1*((double)9*(double)k-(double)8)*(double) ((double)9*(double)k-(double)9)));
  //               }
  //           }
  //
  //       }
  //
  //
  //    }
  //
  //   static void sieveOfEratosthenes(int n)
  //    {
  //        boolean prime[] = new boolean[n + 1];
  //        for (int i = 0; i <= n; i++)
  //            prime[i] = true;
  //
  //        for (int p = 2; p * p <= n; p++)
  //        {
  //            if (prime[p] == true)
  //            {
  //                for (int i = p * p; i <= n; i += p)
  //                    prime[i] = false;
  //            }
  //        }
  //
  //        for (int i = 2; i <= n; i++)
  //        {
  //            if (prime[i] == true)
  //                treeMap.put(i,0);
  //        }
  //    }
  //    static TreeMap<Integer,Integer> treeMap;
  //    static class comp implements Comparator<Point> {
  //        public int compare(Point a, Point b) {
  //            if (b.y == a.y) {
  //                return a.x - b.x;
  //            }
  //            return b.y - a.y;
  //        }
  //    }
  
      static boolean ff = false;
  
      //    static void maxx(int ind,int l,int r,int d,int u,int n)
  //    {
  //        if(ind==4){
  //            if(l<0 || r<0 || u<0 || d<0){
  //                return;
  //            }
  //            ff=true;
  //            return;
  //        }
  //        if(ind==0){
  //            if(l==n){
  //                maxx(ind+1,l-2,r,d-1,u-1,n);
  //            }else if(l==n-1){
  //                maxx(ind+1,l-1,r,d-1,u,n);
  //                if(ff){
  //                    return;
  //                }
  //                maxx(ind+1,l-1,r,d,u-1,n);
  //            }else{
  //                maxx(ind+1,l,r,d,u,n);
  //            }
  //
  //        }else if(ind==1){
  //            if(r==n){
  //                maxx(ind+1,l,r-2,d-1,u-1,n);
  //            }else if(r==n-1){
  //                maxx(ind+1,l,r-1,d-1,u,n);
  //                if(ff){
  //                    return;
  //                }
  //                maxx(ind+1,l,r-1,d,u-1,n);
  //            }else{
  //                maxx(ind+1,l,r,d,u,n);
  //            }
  //
  //        }else if(ind==2){
  //            if(d==n){
  //                maxx(ind+1,l-1,r-1,d-2,u,n);
  //            }else if(d==n-1){
  //                maxx(ind+1,l-1,r,d-1,u,n);
  //                if(ff){
  //                    return;
  //                }
  //                maxx(ind+1,l,r-1,d-1,u,n);
  //            }else{
  //                maxx(ind+1,l,r,d,u,n);
  //            }
  //
  //        }else{
  //            if(u==n){
  //                maxx(ind+1,l-1,r-1,d,u-2,n);
  //            }else if(u==n-1){
  //                maxx(ind+1,l-1,r,d,u-1,n);
  //                if(ff){
  //                    return;
  //                }
  //                maxx(ind+1,l,r-1,d,u-1,n);
  //            }else{
  //                maxx(ind+1,l,r,d,u,n);
  //            }
  //        }
  //    }
  //    static void filereader() throws IOException{
  //        FileReader fileReader=new FileReader("input.txt");
  //        int ch;
  //        String str="";
  //        StringBuilder stringBuilder=new StringBuilder();
  //        while ((ch=fileReader.read())!=-1)
  //            stringBuilder.append((char)ch);
  //
  //        fileReader.close();
  //        StringBuilder ans=new StringBuilder();
  //        FileWriter fw=new FileWriter("output.txt");
  //        for(int j=0;j<ans.length();j++){
  //            fw.write(ans.charAt(j));
  //        }
  //        fw.close();
  //    }
  //    static class point {
  //        int w, v;
  //
  //        point(int v, int w) {
  //            this.v = v;
  //            this.w = w;
  //        }
  //    }
  //
  //    static class compp implements Comparator<point> {
  //        public int compare(point a, point b) {
  //            return b.v - a.v;
  //        }
  //    }
  
      //    static int cal(int ind,String s,String x,int val){
  //        if(ind>=s.length()){
  //            if(val%7==0){
  //                return 1;
  //            }else{
  //                return 0;
  //            }
  //        }
  //        if(aa[ind][val]!=-1){
  //            return aa[ind][val];
  //        }
  //
  //        if(x.charAt(ind)=='A'){
  //            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
  //            return aa[ind][val]=Math.min( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
  //        }else{
  //            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
  //            return aa[ind][val]=Math.max( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
  //        }
  //
  //    }
  //    static int aa[][];
  
      //    static long calculateWays(int ind,int bit,int[] primes,long a,long b,int[] flags){
  //
  //        long num=(long)((long)ind+(long)a);
  //        if(num>b){
  //            return 1;
  //        }
  //        if(aaa[ind][bit]!=-1){
  //            return aaa[ind][bit];
  //        }
  //
  //        long tot=0;
  ////        int flag=0;
  ////        int bitt=bit;
  ////        for(int j=0;j<primes.length;j++){
  ////            int jj= (int)bit & (int)Math.pow(2,j);
  ////
  ////            if(jj!=0 && num%(long)primes[j]==0 ){
  ////                flag=1;
  ////                break;
  ////            }
  ////            if( num%(long)primes[j]==0 ){
  ////                bitt=(int)bitt | (int)Math.pow(2,j);
  ////
  ////            }
  ////        }
  //        int jj=(int)(flags[ind] & (int)bit);
  //        if( jj==0){
  //            tot=(long)((long)tot+(long)calculateWays(ind+1,bit | flags[ind],primes,a,b,flags));
  //            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
  //
  //        }else{
  //            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
  //        }
  //
  //        return aaa[ind][bit]=tot;
  //    }
  //    static long[][] aaa;
  //
  //    static long maxx(String str, int n, long val) {
  //
  //        if (hashMap.get(str) != null) {
  //            return hashMap.get(str);
  //        }
  //        long tot = 0;
  //        if (str.equals("")) {
  //            for (int j = 1; j <= 9; j++) {
  //                tot = tot + maxx(str + String.valueOf(j), n, val);
  //            }
  //            hashMap.put(str, tot);
  //
  //            return tot;
  //        } else {
  //            String ss = str + str;
  //            if (Long.parseLong(ss) > val) {
  //                return 0;
  //            }
  //            if (str.length() == n) {
  //                return 1;
  //            }
  //            for (int j = 0; j <= 9; j++) {
  //                tot = tot + maxx(str + String.valueOf(j), n, val);
  //            }
  //            hashMap.put(str, tot);
  //            return tot;
  //        }
  //
  //    }
  //
  //    static class poi {
  //        int freq, occur, num;
  //
  //        poi(int freq, int occur, int num) {
  //            this.freq = freq;
  //            this.num = num;
  //            this.occur = occur;
  //        }
  //    }
  //
  //    static class poii {
  //        int day, tot;
  //
  //        poii(int day, int tot) {
  //            this.day = day;
  //            this.tot = tot;
  //        }
  //    }
  //
  //    static class comp2 implements Comparator<poii> {
  //        public int compare(poii a, poii b) {
  //            return a.tot - b.tot;
  //        }
  //    }
  //
  //    static class comp1 implements Comparator<poi> {
  //        @Override
  //        public int compare(poi o1, poi o2) {
  //            if (o2.occur == o1.occur) {
  //                return o1.freq - o2.freq;
  //            }
  //            return o1.occur - o2.occur;
  //        }
  //    }
  
      static long gcd(long a, long b) {
          if (b == 0)
              return a;
          return gcd(b, a % b);
      }
  
  //    static HashMap<String, Long> hashMap;
  
  //    static class poit {
  //        int freq, val;
  //
  //        poit(int freq, int val) {
  //            this.freq = freq;
  //            this.val = val;
  //        }
  //    }
  
  //    static class com implements Comparator<poit> {
  //        public int compare(poit a, poit b) {
  //            return b.freq - a.freq;
  //        }
  //    }
  
  
  //    static int maxx(int ind,String str,int prev,int x,int y){
  //        if(ind>=str.length()){
  //            return 0;}
  //        if(aa[ind][prev]!=Integer.MAX_VALUE){
  //            return aa[ind][prev];}
  //        if(str.charAt(ind)=='?' ){
  //            if(ind>0){
  //                if(prev==1){
  //                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
  //                             return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x+y );
  //
  //                    }
  //                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
  //                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y)+x );
  //
  //                    }
  //                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
  //                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
  //                    }
  //                    else{
  //                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y ),maxx(ind+1,str,2,x,y)+x);
  //                    }
  //
  //                }
  //                else{
  //                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
  //                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y)+y );
  //
  //                    }
  //                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
  //                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x+y,maxx(ind+1,str,2,x,y) );
  //
  //                    }
  //                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
  //                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y) );
  //                    }
  //                    else{
  //                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y )+y,maxx(ind+1,str,2,x,y));
  //                    }
  //                }
  //            }
  //            else{
  //                if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
  //                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
  //
  //                }
  //                else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
  //                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y) );
  //
  //                }
  //                else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
  //                    return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y) );
  //                }
  //                else{
  //                    return aa[ind][prev]=0;
  //                }
  //            }
  //        }else if(str.charAt(ind)=='C'){
  //            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
  //                return aa[ind][prev]=maxx(ind+1,str,1,x,y);
  //
  //            }
  //            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
  //                return aa[ind][prev]=maxx(ind+1,str,1,x,y)+x;
  //
  //            }
  //            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
  //                return aa[ind][prev]=  maxx(ind+1,str,1,x,y);
  //            }
  //            else{
  //                return aa[ind][prev]=0;
  //            }
  //        }
  //        else{
  //            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
  //                return aa[ind][prev]=maxx(ind+1,str,2,x,y)+y;
  //
  //            }
  //            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
  //                return aa[ind][prev]=maxx(ind+1,str,2,x,y);
  //
  //            }
  //            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
  //                return aa[ind][prev]=  maxx(ind+1,str,2,x,y);
  //            }
  //            else{
  //                return aa[ind][prev]=0;
  //            }
  //        }
  //    }
  //    static int[][] aa;
  //    static int totalCost(int[] arr,int[] arr1,int n){
  //        HashMap<Integer,Integer> has=new HashMap<>();
  //        for(int i=0;i<n;i++){
  //
  //            has.put(arr[i],i );
  //
  //        }
  //        Arrays.sort(arr1);
  //        int tot=0;
  //        for(int i=0;i<n-1;i++){
  //            tot=tot+has.get(arr1[i])-i+1;
  //            int tta=has.get(arr1[i]);
  //            for(int j=tta;j>=i;j-- ){
  //                has.put(arr[j],tta-j+i );
  //
  //            }
  //            int low=i;
  //            int high=tta;
  //            while(low<high){
  //                int temp=arr[low];
  //                arr[low]=arr[high];
  //                arr[high]=temp;
  //                low++;high--;
  //            }
  //
  //        }
  //        return tot;
  //
  //    }
  //    static boolean fff=false;
  //    static HashSet<String> hashSet=new HashSet<>();
  //    static void maxx(int ind,int[] arr,HashSet<Integer> has,int n,String str,int cost){
  //        if(ind==n){
  //            int to=totalCost(arr,arr,n);
  //            if(to==cost){
  //                fff=true;
  //            }
  //            return;
  //        }
  //        if(hashSet.contains(str)){
  //            return ;
  //        }
  //        for(int j=1;j<=n;j++){
  //            if(!has.contains(j)){
  //                arr[ind]=j;
  //                has.add(j);
  //                maxx(ind+1,arr,has,n,str+String.valueOf(j),cost);
  //                has.remove(j);
  //            }
  //            if(ff){
  //                return;
  //            }
  //        }
  //    }
  //    static long maxx(int ind,int n,int flag,int k){
  //        if(ind>n || ind<0 || k==1){
  //            return 0;
  //        }
  //        if(flag==1 && ind==0){
  //            return 0;
  //        }
  //        if(aaaa[ind][flag][k]!=-1) {
  //            return aaaa[ind][flag][k];
  //        }
  //        if(flag==0){
  //            return aaaa[ind][flag][k]=(long)(maxx(ind-1,n,1,k-1)+(long)1+maxx(ind+1,n,0,k))%(long)mod;
  //        }
  //        else{
  //            return aaaa[ind][flag][k]=(long)(maxx(ind+1,n,0,k-1)+(long)1+maxx(ind-1,n,1,k))%(long)mod;
  //        }
  //
  //    }
  //
  ////    static int minimum_change(int ind,int[] arr,int tot,int flag,String str,String temp){
  ////        if(ind>=arr.length){
  ////            return 0;
  ////        }
  ////        if(tot>=5) {
  ////            String strr=String.valueOf(arr[ind]);
  ////            for(int j=0;j<=9;j++) {
  ////                strr=strr.concat(String.valueOf(j));
  ////            }
  ////        }
  ////    }
  //
  //    static long[][][] aaaa;
  //    static long mod=(long)((long)Math.pow(10,9)+(long)7);
  //    static List<Integer> ans=new ArrayList<>();
  //    static void goodVertices(LinkedList<Integer>[] linkedLists,int src,int parent,HashSet<Integer> hashSet,int[] cost){
  //
  //        int flag=0;
  //        if(!hashSet.contains(cost[src])){
  //            hashSet.add(cost[src]);
  //            ans.add(src+1);
  //            flag=1;
  //        }
  //        for(Integer i:linkedLists[src]){
  //            if(i==parent){
  //                continue;
  //            }
  //            goodVertices(linkedLists,i,src,hashSet,cost);
  //        }
  //        if(flag==1){
  //            hashSet.remove(cost[src]);
  //        }
  //
  //    }
  //    static boolean fla=false;
  //    static void calculate(String[] str,int flag,String str1,String str2){
  //        if(flag==0){
  //            if(str[0].length()==str1.length()){
  //                calculate(str,1,str1,str2);
  //                return;
  //            }
  //            for(int j=0;j<=9;j++){
  //                if( j==0 && str1.equals("") ){
  //                    continue;
  //                }
  //                calculate(str,1,str1+String.valueOf(j),str2);
  //                if(fla){
  //                    break;
  //                }
  //            }
  //        }
  //        else if(flag==1){
  //            if(str[1].length()==str2.length()){
  //                calculate(str,2,str1,str2);
  //                return;
  //            }
  //            int ind=str2.length();
  //            if( str[0].length()>ind && str[0].charAt(ind)==str[1].charAt(ind)){
  //                calculate(str,1,str1,str2+String.valueOf(str1.charAt(ind)));
  //            }else{
  //                for(int j=0;j<=9;j++){
  //                    if(j==0 && str2.equals("")){
  //                        continue;
  //                    }
  //                    calculate(str,1,str1,str2+String.valueOf(j));
  //                }
  //            }
  //        }
  //        else{
  //            long n1=Long.parseLong(str1);
  //            long n2=Long.parseLong(str2);
  //            long n3=(long)((long)n1+(long)n2);
  //            if(String.valueOf(n3).length()==str[2].length()){
  //
  //            }
  //
  //        }
  //    }
  //static List<Integer> findprime(int n) {
  //    List<Integer> primes = new ArrayList<>();
  //    boolean[] prime = new boolean[n];
  //    for (int j = 1; j < prime.length; j++) {
  //        prime[j] = true;
  //    }
  //    for (int j = 2; j * j < prime.length; j++) {
  //        if (!prime[j]) {
  //            continue;
  //        }
  //        for (int i = j * j; i < prime.length; i = i + j) {
  //            prime[i] = false;
  //        }
  //    }
  //    for (int j = 2; j < prime.length; j++) {
  //        if (prime[j]) {
  ////            String str=String.valueOf(j);
  ////            hashMap1.putIfAbsent(str.length(),new ArrayList<>());
  ////            hashMap1.get(str.length()).add(j);
  //            primes.add(j);
  //        }
  //    }
  //    return primes;
  //}
  //    static long[][] dp;
  //        static long calculatemin(int low,int high,int[] arr,int flag,long tot){
  //            if(dp[low][high]!=-1){
  //                return dp[low][high];
  //            }
  //            if( low==high){
  //                return 0;
  //            }
  //            return dp[low][high]=Math.min( calculatemin(low+1,high,arr,0,tot),
  //                    calculatemin(low,high-1,arr,0,tot)  )+(long)( (long)arr[high]-(long)arr[low] );
  //        }
  
  
  //        static List<long[]> list=new ArrayList<>();
  //        static HashMap<Integer,List<long[]>> hashMap1;
  //        static void maxx( int src,int parent,LinkedList<Integer>[] lin,HashMap<Point,long[]> hashMap  ){
  //            List<long[]> list1= new ArrayList<>();
  //            list1.addAll(list);
  ////            System.out.println(list1);
  //            hashMap1.put(src,list1);
  //            for(Integer i:lin[src]){
  //                if(i==parent){
  //                    continue;
  //                }
  //                list.add(hashMap.get(new Point(src,i)));
  //                maxx(i,src,lin,hashMap);
  //                list.remove(list.size()-1);
  //            }
  //        }
  //    static class com1 implements Comparator<long[]>{
  //            public int compare(long[] a,long[] b){
  //                return Long.compare(b[2],a[2]);
  //            }
  //    }
  //    static boolean isFla=false;
  //    static int maxx(int ind,int[] arr,int sum){
  //        if(sum==0){
  //            isFla=true;
  //            return 0;
  //        }
  //            if(ind>=arr.length || sum<0){
  //                return 0;
  //            }
  //
  //            if(pp[ind][sum] != -1){
  //                return pp[ind][sum];
  //            }
  //        maxx(ind+1,arr,sum-arr[ind]);
  //            if(isFla){
  //                return 0;
  //            }
  //
  //            return pp[ind][sum]=maxx(ind+1,arr,sum);
  //
  //    }
  //    static int[][] pp;
  //    static int maxx(int ind,int[] arr,int sum,int i){
  //
  //        if(sum==0){
  //            isFla=true;
  //            return 0;
  //        }
  //        if(ind>=arr.length || sum<0){
  //            return 0;
  //        }
  //
  //        if(pp[ind][sum] != -1){
  //            return pp[ind][sum];
  //        }
  //        if(ind==i){
  //            return pp[ind][sum]=maxx(ind+1,arr,sum,i);
  //        }
  //        maxx(ind+1,arr,sum-arr[ind],i);
  //        if(isFla){
  //            return 0;
  //        }
  //
  //        return pp[ind][sum]=maxx(ind+1,arr,sum,i);
  //
  //    }
  //     static int[] st;
  //    public static int[] constructSegmentTree(int[] arr)
  //    {
  //        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
  //        int size = 2*(int)Math.pow(2, height)-1;
  //        st = new int[size];
  //        constructST(arr, 0, arr.length-1, 0);
  //        return st;
  //    }
  //
  //    public static int constructST(int[] arr, int ss,
  //                                  int se, int si)
  //    {
  //        if (ss==se)
  //        {
  //            st[si] = arr[ss];
  //            return st[si];
  //        }
  //        int mid = ss+(se-ss)/2;
  //        st[si] = gcd(constructST(arr, ss, mid, si*2+1),
  //                constructST(arr, mid+1, se, si*2+2));
  //        return st[si];
  //    }
  //
  //    // Function to find gcd of 2 numbers.
  //    private static int gcd(int a, int b)
  //    {
  //        if (a < b)
  //        {
  //            // If b greater than a swap a and b
  //            int temp = b;
  //            b = a;
  //            a = temp;
  //        }
  //
  //        if (b==0)
  //            return a;
  //        return gcd(b,a%b);
  //    }
  //
  //    public static int findRangeGcd(int ss, int se, int[] arr)
  //    {
  //        int n = arr.length;
  //
  //        if (ss<0 || se > n-1 || ss>se)
  //            throw new IllegalArgumentException("Invalid arguments");
  //
  //        return findGcd(0, n-1, ss, se, 0);
  //    }
  //
  //    public static int findGcd(int ss, int se, int qs, int qe, int si)
  //    {
  //        if (ss>qe || se < qs)
  //            return 0;
  //
  //        if (qs<=ss && qe>=se)
  //            return st[si];
  //
  //        int mid = ss+(se-ss)/2;
  //
  //        return gcd(findGcd(ss, mid, qs, qe, si*2+1),
  //                findGcd(mid+1, se, qs, qe, si*2+2));
  //    }
  //
  //    static class po{
  //        int id;
  //        int val;
  //        po(int id,int val){
  //            this.id=id;
  //            this.val=val;
  //        }
  //    }
  //    static class compara implements Comparator<po>{
  //        public int compare(po a,po b){
  //            return b.val-a.val;
  //        }
  //    }
  
  //    static boolean[] vis;
  //    static boolean[] origvis;
  //    static boolean[] colr;
  //    static boolean[] colb;
  //    static boolean[] colg;
  //    static int tot=0;
  //    static int[] colo;
  //    static long coloring(int src,LinkedList<Integer>[] lin,int color,int n){
  //        tot++;
  //        origvis[src]=true;
  //        if(color==1){
  //            colr[src]=true;
  //        }else if(color==2){
  //            colb[src]=true;
  //        }else{
  //            colg[src]=true;
  //        }
  //        vis[src]=true;
  //        colo[src]=color;
  //        boolean flag=false;
  //        long tott=(long)0;
  //        for(Integer j:lin[src]){
  //            if(!vis[j] ){
  //
  //                HashSet<Integer> hashSet=new HashSet<>();
  //                for(Integer i:lin[j]){
  //                    hashSet.add(colo[i]);
  //                }
  //                hashSet.add(color);
  //                for(int i=1;i<=3;i++){
  //                    if(!hashSet.contains(i)  ){
  //                        if(i==1 && !colr[j]) {
  //                            flag = true;
  //                            tott = (long) ((long) tott + (long) coloring(j, lin, i, n));
  //                        }
  //                        else if( i==2 && !colb[j] ){
  //                            flag = true;
  //                            tott = (long) ((long) tott + (long) coloring(j, lin, i, n));
  //
  //                        }else if(i==3 && !colg[j]){
  //                            flag = true;
  //                            tott = (long) ((long) tott + (long) coloring(j, lin, i, n));
  //
  //                        }
  //                    }
  //                }
  //
  //            }
  //        }
  //        vis[src]=false;
  //        colo[src]=0;
  //        tot--;
  //        if(!flag){
  //            return 1;
  //        }
  ////        System.out.println(tott);
  //        return tott;
  //    }
  
  //    static int maxx(int ind,int[] a,int[] b,int[] c,int[] d,int[] e){
  //        if(ind>=a.length){
  //            return 0;
  //        }
  //
  //
  //    }
  //FileWriter fr=new FileWriter("/home/vaibhav/Desktop/output.txt");
  //    String str="my name is vaibhav kumar";
  //        for(int j=0;j<str.length();j++){
  //        fr.write(str);
  //        fr.write("\n");
  //    }
  //        fr.close();
  //    //        int[] arr=new int[]{1,2,3,42,53};
  ////        for(int j=0;j<arr.length;j++){
  ////            fr.write(String.valueOf(arr[j]));
  ////        }
  ////        fr.close();
  ////        FileReader fileReader=new FileReader("/home/vaibhav/Desktop/output.txt");
  //    StringBuilder stringBuilder=new StringBuilder();
  //    //        int ch;
  ////        while((ch=fileReader.read())!=-1){
  ////            stringBuilder.append((char)ch);
  ////        }
  ////        fileReader.close();
  //    BufferedReader br=new BufferedReader(new FileReader(new File("/home/vaibhav/Desktop/output.txt")));
  //    String st;
  //        while ( (st=br.readLine())!=null ){
  ////            stringBuilder.append(st);
  //        System.out.println(st);
  //    }
  ////        System.out.println(stringBuilder.toString());
  
  
      static class point {
          int val;
          String name;
  
      }
  
      static class comp implements Comparator<point> {
          public int compare(point a, point b) {
              return a.val - b.val;
          }
      }
  
      // static HashSet<String> hashSet;
  //    static void maxx(int tot, List<Character> comp, List<Character> prob, String str ){
  //        if(tot==4 ){
  //            HashSet<Character> ch=new HashSet<>();
  //            for(int j=0;j<4;j++){
  //                ch.add(str.charAt(j));
  //            }
  //            for(Character chh:comp){
  //                   if(!ch.contains(chh)){
  //                       return ;
  //                   }
  //            }
  //            hashSet.add(str);
  //            return ;
  //        }
  //
  //        for(int j=0;j<comp.size();j++){
  //            maxx(tot+1,comp,prob,str+String.valueOf(comp.get(j)));
  //        }
  //        for(int j=0;j<prob.size();j++){
  //            maxx(tot+1,comp,prob,str+String.valueOf(prob.get(j)));
  //        }
  //        return;
  //
  //    }
  //static int[][][] aa;
  //    static int maxx(int x,int y,List<String> lis,int flag){
  //        if(aa[x][y][flag]!=Integer.MIN_VALUE){
  //            return aa[x][y][flag];
  //        }
  //        if(flag==0){
  //            int max=Integer.MIN_VALUE;
  //            if( x+1<lis.size()  ){
  //                if( lis.get(x+1).charAt(y)=='+' ){
  //                max=Math.max( maxx(x+1,y,lis,1 )+1,max );}
  //                else{
  //                    max=Math.max( maxx(x+1,y,lis,1)-1,max );
  //                }
  //            }
  //            if(y+1< lis.get(0).length() ){
  //                if( lis.get(x).charAt(y+1)=='+' ){
  //                    max=Math.max( maxx(x,y+1,lis,1 )+1,max );}
  //                else{
  //                    max=Math.max( maxx(x,y+1,lis,1)-1,max );
  //                }
  //            }
  //            if(max==Integer.MIN_VALUE){
  //                return aa[x][y][flag]=0;
  //            }
  //            return aa[x][y][flag]=max;
  //
  //        }else{
  //            int max=Integer.MAX_VALUE;
  //            if( x+1<lis.size()  ){
  //                if( lis.get(x+1).charAt(y)=='+' ){
  //                    max=Math.min( maxx(x+1,y,lis,0 )-1,max );
  //                }
  //                else{
  //                    max=Math.min( maxx(x+1,y,lis,0)+1,max );
  //                }
  //            }
  //            if(y+1< lis.get(0).length() ){
  //                if( lis.get(x).charAt(y+1)=='+' ){
  //                    max=Math.min( maxx(x,y+1,lis,0 )-1,max );}
  //                else{
  //                    max=Math.min( maxx(x,y+1,lis,0)+1,max );
  //                }
  //            }
  //            if(max==Integer.MAX_VALUE){
  //                return aa[x][y][flag]=0;
  //            }
  //            return aa[x][y][flag]=max;
  //        }
  //
  //    }
  //static class compp implements Comparator<int[]>{
  //    public int compare(int[] a,int[] b){
  //        return a[2]-b[2];
  //    }
  //}
  //
  //static int maxx(int j){
  //    if(j>1){
  //        j=maxx(j/10)+maxx(j%10);
  //
  //    }else{
  //        j=0;
  //    }
  //    return j;
  //}
  //    static long maxx(int flag,int ind,String str,int k,int n){
  //       if(ind>=n){
  //           return 1;
  //       }
  //       if(aa[ind][flag]!=-1){
  //           return aa[ind][flag];
  //       }
  //       if(flag==0){
  ////           int mm = Math.min(k,str.charAt(ind)-'0');
  ////           mm = Math.min(mm,str.charAt(str.length()-1-ind)-'0');
  //           long tot=maxx(0,ind+1,str,k,n)%mod;
  //           for(int j=0;j<k;j++){
  //               int ch = str.charAt(ind)-'0';
  //               int ch1 = str.charAt(str.length()-1-ind)-'0';
  //               if(k>ch){
  //                   break;
  //               }
  //               if(k<ch && k<=ch1){
  //                   tot=(long)((long)tot+(long)maxx(1,ind+1,str,k,n))%(long)mod;
  //               }
  //               else if(k==ch && k<=ch1){
  //
  //               }
  //
  //
  //
  //
  //           }
  //           return aa[ind][flag]=tot;
  //
  //       }else{
  //           long tot=0;
  //           for(int j=1;j<=k;j++){
  //               tot=(long)((long)tot+(long)maxx(1,ind+1,str,k,n))%(long)mod;
  //           }
  //           return aa[ind][flag]=tot;
  //       }
  //
  //
  //    }
  //static HashSet<String> hashSet;
  //    static HashSet<String> hashset;
  //    static int maxx(String str,String st,int n,int ind,int k){
  //        if(ind>=str.length()){
  //            int i=0,j=st.length()-1;
  //            int flag=0;
  //            while(i<j){
  //                if(st.charAt(i)!=st.charAt(j)){
  //                    flag=1;break;
  //                }
  //                i++;j--;
  //            }
  //            if(flag==0 && str.compareTo(st)>0 ){
  //                hashSet.add(st);
  //            }
  //            return 0;
  //        }
  //        if(hashset.contains(st)){
  //            return 0;
  //        }
  //        for(int j=0;j<k;j++){
  //            char ch=(char)('a'+j);
  //            maxx(str,st+String.valueOf(ch),n,ind+1,k);
  //        }
  //        hashset.add(st);
  //        return 0;
  //    }
  //    static class TreeNode{
  //        char ch;
  //        TreeNode left,right;
  //        TreeNode(char ch){
  //            this.ch=ch;
  //        }
  //    }
  //    static void Java(){
  //        try{
  //            System.out.println("Inside Java");
  //            throw new RuntimeException("demo");
  //        }
  //        finally {
  //            System.out.println("Java's finally");
  //        }
  //    }
  //    static void Python(){
  //        try{
  //            System.out.println("Inside Python");
  //            return;
  //        }
  //        finally {
  //            System.out.println("Python's finally");
  //        }
  //    }
  //
  ////    static long[][] aa;
  ////    static long mod=(long)((long)Math.pow(10,9)+(long)7);
  //    static void postorder(TreeNode root){
  //        if(root==null){
  //            return;
  //        }
  //        postorder(root.left);
  //        postorder(root.right);
  //        System.out.println(root.ch);
  //    }
  //    static boolean fff=false;
  //    static void maxx(List<Integer> lis,int ind,long n){
  //        if(ind>=lis.size()){
  //            return;
  //        }
  //        if(n<0){
  //            return;
  //        }
  //        if(n==0){
  //            fff=true;
  //            return;
  //        }
  //
  //
  //
  //        maxx(lis,ind+1,n);
  //        if(fff){
  //            return;
  //        }
  //        long tt=lis.get(ind);
  //        while(true){
  //            n=n-tt;
  //            if(n<0){
  //                break;
  //            }
  //            for(int i=0;i<lis.size();i++){
  //                if(n%lis.get(i)==0){
  //                    fff=true;
  //                    break;
  //                }
  //            }
  //            maxx(lis,ind,n);
  //            if(fff){
  //                return;
  //            }
  //
  //        }
  //
  //    }
  //    static class compy implements Comparator<long[]> {
  //
  //        public int compare(long[] a,long[] b) {
  //
  //        return Long.compare(a[0],b[0]);
  //        }
  //
  //    }
      static int[] prime;
  
  
  
  
  //    static long maxx(int ind, long arr[], int flag,int k,int tot) {
  //        if (ind >= arr.length && tot < k) {
  //            return Integer.MIN_VALUE;
  //        }
  //        if (ind >= arr.length) {
  //            return 0;
  //        }
  //        if(flag==0 && k==tot){
  //            return 0;
  //        }
  //        if (aa[ind][flag][tot] != Integer.MAX_VALUE) {
  //            return aa[ind][flag][tot];
  //        }
  //        if(flag==0){
  //            return aa[ind][flag][tot]=Math.max( maxx(ind+1,arr,0,k,tot),maxx(ind+1,arr,1,k,tot+1)+(tot+1)*arr[ind] );
  //        }else{
  //            return aa[ind][flag][tot]=Math.max( maxx(ind+1,arr,1,k,tot)+tot*arr[ind],maxx(ind,arr,0,k,tot)  );
  //        }
  //    }
  //
  //    static long[][][] aa;
  
  //    static int maxx(int ind,int[] arr){
  //        if(ind-1<0){
  //            return arr[0];
  //        }
  //        if(aa[ind]!=Integer.MAX_VALUE){
  //            return aa[ind];
  //        }
  //        int min=Integer.MAX_VALUE;
  //        min=maxx(ind-1,arr)-arr[ind];
  //        min=Math.min( min,maxx(ind-1,arr)+arr[ind] );
  //        if(arr[ind]<0){
  //
  //        }
  //        min=Math.min(min,maxx(ind-1,arr)*arr[ind]);
  //        return aa[ind]=min;
  //    }
  //static int[][] aa;
  //    static boolean[] vis;
  //    static long tot=0;
  //    static void maxx(int src,LinkedList<Integer>[] lin){
  //        vis[src]=true;
  //        tot=(long)(tot+(long)1);
  //        for(Integer i:lin[src]){
  //            if(vis[i]){
  //                continue;
  //            }
  //            maxx(i,lin);
  //        }
  ////        vis[src]=false;
  //    }
  //    static int min=Integer.MAX_VALUE;
  //    static int maxx(int ind,int[] arr,int sum,int tot){
  //        if(ind>=arr.length){
  //            int tt=Math.max( tot,sum-tot );
  //            min=Math.min(tt,min);
  //            return 0;
  //        }
  //        if(aa[ind][tot]!=-1){
  //            return aa[ind][tot];
  //        }
  //        return aa[ind][tot]=maxx(ind+1,arr,sum,tot+arr[ind])+maxx(ind+1,arr,sum,tot);
  //
  //    }
  
  
      static class com implements Comparator<long[]> {
          public int compare(long[] a, long[] b) {
              return Long.compare(a[0], b[0]);
          }
      }
  
      static class comm implements Comparator<long[]> {
          public int compare(long[] a, long[] b) {
              return Long.compare(a[1], b[1]);
          }
      }
  
      static int root(int a, int[] num) {
          while (a != num[a]) {
              num[a] = num[num[a]];
              a = num[a];
          }
          return a;
      }
  
      static int roott(int a, int num[]) {
          while (a != num[a]) {
              num[a] = num[num[a]];
              a = num[a];
          }
          return a;
      }
  
      static class compa implements Comparator<int[]> {
          public int compare(int[] a, int[] b) {
              return a[0] - b[0];
          }
      }
  
      static void maxx(int src, int d, int parent, LinkedList<Integer>[] lin) {
          if (d % 2 == 0) {
              even.add(src);
          } else {
              odd.add(src);
          }
          for (Integer v : lin[src]) {
              if (v != parent) {
                  maxx(v, d + 1, src, lin);
              }
          }
      }
  
      static boolean fff = false;
  
      static void mmax(String str, int start, int end, int ind) {
          if (start < 0 && end >= str.length()) {
              fff = true;
              return;
          }
          char ch = (char) (ind + 'a');
          if (start >= 0 && str.charAt(start) == ch) {
              mmax(str, start - 1, end, ind + 1);
          }
          if (start == end) {
              return;
          }
          if (end < str.length() && str.charAt(end) == ch) {
              mmax(str, start, end + 1, ind + 1);
          }
      }
  
      static HashSet<Integer> odd, even;
      static long maxx(int x,int y,int[][] a ,long c,int flag){
          if(aa[x][y][flag]!=-1){
              return aa[x][y][flag];
          }
          if(flag==0){
              long min = Long.MAX_VALUE;
              if (x + 1 < a.length) {
                  min = Math.min((long)((long)maxx(x+1,y,a,c,1)+(long)c+(long)a[x][y]), (long)maxx(x + 1, y, a, c,0) );
              }
  
              if (y + 1 < a[0].length) {
                  min = Math.min(min,(long)maxx(x, y + 1, a, c,0) );
                  min = Math.min(min,(long)((long)maxx(x,y+1,a,c,1)+(long)c+(long)a[x][y]) );
              }
  
  
              return aa[x][y][flag]=min;
  
          }else {
              long min = (long)a[x][y];
              if (x + 1 < a.length) {
                  min = Math.min(min, (long)((long)maxx(x + 1, y, a, c,1) + (long)c));
              }
  
              if (y + 1 < a[0].length) {
                  min = Math.min(min, (long)((long)maxx(x, y + 1, a, c,1) + (long) c) );
              }
              return aa[x][y][flag]=min;
          }
  
  
      }
      static long[][][] aa;
      static void dfs(int x,int y){
          int[][] dis=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
          for(int j=0;j<dis.length;j++){
              if(valid(dis[j][0]+x,dis[j][1]+y)){
                  vis[x+dis[j][0]][y+dis[j][1]]=true;
                  dfs(x+dis[j][0],y+dis[j][1]);
              }
          }
      }
      static boolean valid(int x,int y){
          if(x<0 || y<0 || x>=stringBuilders.length || y>=stringBuilders[0].length() || vis[x][y] ){
              return false;
          }
          return true;
      }
      static boolean valid1(int x,int y){
          if(x<0 || y<0 || x>=stringBuilders.length || y>=stringBuilders[0].length() || vis1[x][y]  ){
              return false;
          }
          return true;
      }
      static boolean[][] vis,vis1;
      static HashSet<StringBuilder[]> hashSet;
  //    static boolean maxx(int k,int x,int y){
  //        if(k==0){
  //            vis=new boolean[stringBuilders.length][stringBuilders[0].length()];
  //            dfs(x,y);
  //            for(int j=0;j<stringBuilders.length;j++){
  //                for(int i=0;i<stringBuilders[0].length();i++){
  //                    if(stringBuilders[j].charAt(i)=='#' && !vis[j][i] ){
  //                        return false;
  //                    }
  //                }
  //            }
  //            StringBuilder stringBuilder[]=stringBuilders.clone();
  //            hashSet.add(stringBuilder);
  //            return true;
  //        }
  //        if(stringBuilders[x].charAt(y)=='.'){
  //            stringBuilders[x].setCharAt(y,'#');
  //            int[][] dis=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
  //            for(int j=0;j<dis.length;j++){
  //                if(valid1(dis[j][0]+x,dis[j][1]+y)){
  //                    vis1[x+dis[j][0]][y+dis[j][1]]=true;
  //
  //                    if(maxx(k-1,x+dis[j][0],y+dis[j][1])){}
  //                    vis1[x+dis[j][0]][y+dis[j][1]]=false;
  //                }
  //            }
  //            stringBuilders[x].setCharAt(y,'.');
  //            for(int j=0;j<dis.length;j++){
  //                if(valid1(dis[j][0]+x,dis[j][1]+y)){
  //                    vis1[x+dis[j][0]][y+dis[j][1]]=true;
  //
  //                    if(maxx(k,x+dis[j][0],y+dis[j][1])){}
  //                    vis1[x+dis[j][0]][y+dis[j][1]]=false;
  //                }
  //            }
  //        }else{
  //            int[][] dis=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
  //            for(int j=0;j<dis.length;j++){
  //                if(valid1(dis[j][0]+x,dis[j][1]+y)){
  //                    vis1[x+dis[j][0]][y+dis[j][1]]=true;
  //
  //                    if(maxx(k,x+dis[j][0],y+dis[j][1])){}
  //                    vis1[x+dis[j][0]][y+dis[j][1]]=false;
  //                }
  //            }
  //        }
  //        return false;
  //    }
      public interface Flyer { int j =5;}
      static StringBuilder[] stringBuilders;
      static int k=0;
      static void sieveOfEratosthenes(int n) {
          boolean primes[] = new boolean[n + 1];
          for (int i = 0; i <= n; i++)
              primes[i] = true;
  
          for (int p = 2; p * p <= n; p++) {
              if (primes[p]) {
                  for (int i = p * p; i <= n; i += p) {
                      primes[i] = false;
  
                  }
              }
          }
  
  
          for (int i = 2; i <= n; i++) {
              if(primes[i]){
                  pr.add(i);
              }
          }
      }
  
      static long maxx(int ind,int k,long t1,long t2,int flag){
          if(ind==k){
              return 1l;
          }
          if(dpp[ind][flag]!=-1){
              return dpp[ind][flag];
          }
          if(flag==0){
              return  dpp[ind][flag]= (long)((long)((long)maxx(ind+1,k,t1,t2,0)*(long)t1)%(long)mod+(long)((long)maxx(ind+1,k,t1,t2,1)*(long)1)%mod)%mod;
          }else{
              return  dpp[ind][flag]= (long)((long)((long)maxx(ind+1,k,t1,t2,1)*(long)t2)%(long)mod);
          }
      }
      static long maxx(int ind,int k,int flag){
          if(ind==k){
              if(flag==0){
                  return 0l;
              }
              return 1l;
          }
          if(dpp[ind][flag]!=-1){
              return dpp[ind][flag];
          }
          if(flag==0) {
              return dpp[ind][flag] = (long) ((long) maxx(ind + 1, k,0) + (long) maxx(ind + 1, k,1)) % mod;
          }else{
              return dpp[ind][flag] = (long) ((long) maxx(ind + 1, k,1)*2l ) % mod;
  
          }
      }
      static long mod=(long)((long)Math.pow(10,9)+(long)7);
      static List<Integer> pr;
      static long[][] dpp;
  
      static class comps implements Comparator<int[]> {
          public int compare(int[] a,int[] b){
  
                  return a[0]-b[0];
  
          }
      }
  
      public static int maxEvents(int[][] events) {
  //        point[] pt=new point[events.length];
          PriorityQueue<Integer> pq=new PriorityQueue<>();
  
  //        for(int j=0;j<pt.length;j++){
  //            pt[j]=new point(events[j][0],events[j][1]);
  //        }
  //        Arrays.sort(pt,new comp());
          // int i=pt[0].start+1;
          // int tot=1;
          // for(int j=1;j<pt.length;j++){
          //     // if(pt[j].start>=i){
          //     //     tot++;
          //     //     i=pt[j].start+1;
          //     // }
          //     if(pt[j].start<=i && pt[j].end>=i){
          //         tot++;i=i+1;
          //     }else if(pt[j].start>i){
          //         i=pt[j].start+1;
          //         tot++;
          //     }
          //    // else if(pt[j].start==i && pt[j].start!=pt[j].end ){
          //    //      tot++;
          //    //      i=pt[j].start+1;
          //    //  }
          // }
          int i=0;
          int tot=0;
          int d=-1;
          while(!pq.isEmpty() || i<events.length ){
              if(pq.isEmpty()){
                  d=events[i][0];
              }
              while(i<events.length && events[i][0]<=d ){
                  pq.add(events[i][1]);
                  i++;
              }
              pq.poll();
              d++;
              tot++;
              while(!pq.isEmpty() && pq.peek()<d){
                  pq.poll();
              }
          }
          return tot;
      }
  
     
  
  
      public static void main(String[] args) throws IOException {
  
  
  
          
          Scanner s = new Scanner(System.in);
          int jj=3*(int)Math.pow(10,5);
          int xo=0;
          HashMap<Integer,Integer> hashMap=new HashMap<>();
          hashMap.put(0,0);
          for(int j=1;j<=jj;j++){
              xo=xo^j;
              hashMap.put(j,xo);
          }
  
  
          int t = s.nextInt();
  
          for(int j=0;j<t;j++){
             int a=s.nextInt();
             int b=s.nextInt();
             int ans=a;
             int xor=hashMap.get(ans-1);
             if(xor==b){
                 System.out.println(ans);
                 continue;
             }
             xor=xor^b;
  
             if(xor==a){
                 System.out.println(ans+2);
             }else{
                 System.out.println(ans+1);
             }
          }
  
  
  
  
  
         // int t = s.nextInt();
  
          //for (int j = 0; j < t; j++) {
  //            long n = s.nextLong();
  //            long a1=(long)((long)((long)n/(long)6)*(long)15);
  //            long a2=(long)((long)((long)n/(long)8)*(long)20);
  //            long a3=(long)((long)((long)n/(long)10)*(long)25);
  //            if((long)((long)n%8l)<=6l && (long)((long)n%8l)!=0){
  //                a2=(long)((long)a2+(long)15);
  //            }else if( (long)((long)n%8l) != 0 ){
  //                a2=(long)((long)a2+(long)20);
  //            }
  //
  //            if((long)((long)n%10l)<=6l && (long)((long)n%10l)!=0){
  //                a3=(long)((long)a3+(long)15);
  //            }
  //            else if((long)((long)n%10l)<=8l && (long)((long)n%10l)!=0){
  //                a3=(long)((long)a3+(long)20);
  //            }
  //            else if( (long)((long)n%10l)!=0 ){
  //                a3=(long)((long)a3+(long)25);
  //            }
  //
  //            if((long)((long)n%6l) != 0){
  //                a1=(long)((long)a1+(long)15);
  //            }
  //
  //            System.out.println(Math.min(a1,Math.min(a3,a2)));
  //            System.out.println(a1);
  //            System.out.println(a2);
  //            System.out.println(a3);
  //            int n=s.nextInt();
  //            int[][] num=new int[n][2];
  //            for(int i=0;i<n;i++){
  //                num[i][0]=s.nextInt();
  //            }
  //            for(int i=0;i<n;i++){
  //                num[i][1]=s.nextInt();
  //            }
  //            dp=new long[n][2][2];
  //            for(int i=0;i<n;i++){
  //                for(int k=0;k<2;k++){
  //                    Arrays.fill(dp[i][k],-1);
  //                }
  //            }
  //            System.out.println(maxx(0,0,0,num));
  
          //}
  
      }
      static long[][][] dp;
      static long maxx(int x,int y,int y1,int[][] num){
          int x1=x+y-y1;
          if(x1==num.length-1 && y1==num[0].length-1){
              return 0;
          }
  //        if(dp[x][y][y1] != -1){
  //            return dp[x][y][y1];
  //        }
          long res=0;
          if(x1 != x){
              res=num[x1][y1];
          }
          long max=Integer.MAX_VALUE;
          if(x+1<num.length && y1+1<num[0].length){
              max=maxx(x+1,y,y1+1,num);
          }
          if(x+1<num.length && x1+1<num.length){
              max=Math.min(max,maxx(x+1,y,y1,num));
          }
          if(y+1<num[0].length && x1+1<num.length){
              max=Math.min(max,maxx(x,y+1,y1,num));
          }
          if(y+1<num[0].length && y1+1<num[0].length){
              max=Math.min(max,maxx(x,y+1,y1+1,num));
          }
          if(max==Integer.MAX_VALUE){
              return dp[x][y][y1]=res;
          }
          return dp[x][y][y1]=max+res;
  
  
      }
  
  
  
  
  
  
  
  
  
  
      //
  //        ArrayList obj = new ArrayList(); obj.add("A"); obj.add("B"); obj.add("C"); obj.add(1, "D"); System.out.println(obj); }
  //        for(int i=2;i<5;i++) { for(int j=2;j<5; j+=3) { System.out.println((k+=3) *(++i)); } }
  //        while(i<10 && i >24){
  //            System.out.println("aa");
  //        }
  //        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  //        String stt = br.readLine().trim();
  //        int t = Integer.parseInt(stt);
  //        int q = Integer.parseInt(stt[1]);
  //          Scanner s=new Scanner(System.in);
  //        Scanner scanner=new Scanner(System.in);
  //        int n=scanner.nextInt();
  //        int k= scanner.nextInt();
  //       stringBuilders=new StringBuilder[n];
  //
  //        for(int j=0;j<n;j++){
  //            stringBuilders[j]=new StringBuilder(scanner.next());
  //        }
  //        vis1=new boolean[stringBuilders.length][n];
  //        hashSet=new HashSet<>();maxx(k,0,0);
  //        System.out.println(hashSet.size());
  
  //        HashMap<Integer,HashMap<Integer,List<Integer>>> hashMap=new HashMap<>();
  //        for(int j=0;j<n;j++){
  //            hashMap.put(j,new HashMap<>());
  //            for(int i=0;i<n;i++){
  //                hashMap.get(j).putIfAbsent(aa[j][i],new ArrayList<>());
  //                hashMap.get(j).get(aa[j][i]).add(i);
  //            }
  //        }
  //        List<Integer> ans=new ArrayList<>();
  //        for(Integer i:hashMap.get(0).keySet()){
  //            HashSet<Integer> hashSet=new HashSet<>();
  //            int jaa=hashMap.get(0).get(i).get(0);
  //            hashSet.add(jaa);
  //            hashMap.get(0).get(i).remove(new Integer(jaa));
  //            int flag=0;
  //
  //            for(int j=1;j<n;j++){
  //                if(hashMap.get(j).get(i)!=null) {
  //                    List<Integer> list=hashMap.get(j).get(i);
  //                    int flag1=0;
  //                    for (int k = 0; k < list.size(); k++) {
  //                        int kk=list.get(k);
  //                        if(!hashSet.contains(kk)){
  //                            hashSet.add(kk);
  //                            list.remove(new Integer(kk));
  //                            flag1=1;
  //                            break;
  //                        }
  //                    }
  //                    if(flag1==0){
  //                        flag=1;break;
  //                    }
  //                }else{
  //                    flag=1;
  //                    break;
  //                }
  //            }
  //            if(flag==0){
  //                ans.add(i);
  //            }
  //        }
  //        Reader scanner=new Reader();
  //        int t= scanner.nextInt();
  //        for(int j=0;j<t;j++){
  //            int n= scanner.nextInt();
  //            int[] arr=new int[n];
  //            HashSet<Integer> hashSet=new HashSet<>();
  //            HashMap<Integer, Integer> hashMap=new HashMap<>();
  //            int flag=0;
  //            for(int i=0;i<n;i++){
  //                arr[i]=scanner.nextInt();
  //                if(hashSet.contains(arr[i])){
  //                    flag=1;
  //                }
  //                hashSet.add(arr[i]);
  //            }
  //            if(flag==1){
  //                System.out.println("YES");
  //            }else {
  //                SS:
  //                for (int i = 0; i < n; i++) {
  //                    for (int k = 0; k < n; k++) {
  //                        if(hashSet.contains(arr[i]-arr[k]) || hashSet.contains(arr[k]-arr[i]) )
  //                        {
  //                            flag=1;break SS;
  //                        }
  //                    }
  //                }
  //                if(flag==1){
  //                    System.out.println("YES");
  //                }else{
  //                    List<Integer> list=new ArrayList<>();
  //                    for(int i=0;i<n;i++){
  //                        for(int k=i+1;k<n;k++){
  //                            list.add(arr[k]+arr[i]);
  //                        }
  //                    }
  //                    flag=0;
  //                    for(int i=0;i<list.size();i++){
  //                        HashSet<Integer> hashSet1=new HashSet<>();
  //                        for(int k=0;k<n;k++){
  //                            if(hashSet.contains(list.get(i)-arr[k])  ){
  //                                hashSet1.add(list.get(i)-arr[k]);
  //                            }
  //                            if(hashSet.contains(arr[k]-list.get(i))){
  //                                hashSet1.add(-list.get(i)+arr[k]);
  //                            }
  //                        }
  //                        if(hashSet1.size()>=3){
  //                            flag=1;
  //                            break;
  //                        }
  //                    }
  //                    if(flag==1){
  //                        System.out.println("YES");
  //                    }else {
  //                        list=new ArrayList<>();
  //                        for(int i=0;i<n;i++){
  //                            for(int k=i+1;k<n;k++){
  //                                for(int l=k+1;l<n;l++) {
  //                                    list.add(arr[k] + arr[i]+arr[l]);
  //                                }
  //                            }
  //                        }
  //                        flag=0;
  //                        for(int i=0;i<list.size();i++){
  //
  //                            HashSet<Integer> hashSet1=new HashSet<>();
  //                            for(int k=0;k<n;k++){
  //                                if(hashSet.contains(list.get(i)-arr[k])  ){
  //                                    hashSet1.add(list.get(i)-arr[k]);
  //                                }
  //                                if(hashSet.contains(arr[k]-list.get(i))){
  //                                    hashSet1.add(-list.get(i)+arr[k]);
  //                                }
  //                            }
  //                            if(hashSet1.size()>=4){
  //                                flag=1;
  //                                break;
  //                            }
  //                        }
  //                        if(flag==1){
  //                            System.out.println("YES");
  //                        }else {
  //                            System.out.println("NO");
  //                        }
  //                    }
  //                }
  //            }
  //
  //        }
  
  
  
  
  //int n= scanner.nextInt();
  //int m=scanner.nextInt();
  //LinkedList<Integer>[] linkedLists=new LinkedList[n+1];
  //for(int j=1;j<=n;j++){
  //    linkedLists[j]=new LinkedList<>();
  //}
  //for(int j=0;j<m;j++){
  //    int u= scanner.nextInt();
  //    int v= scanner.nextInt();
  //    linkedLists[u].add(v);
  //    linkedLists[v].add(u);
  //}
  //Queue<Integer> queue=new LinkedList<>();
  //queue.add(1);
  //int[] vis=new int[n+1];
  //Arrays.fill(vis,Integer.MAX_VALUE);
  //vis[1]=0;
  //long[] paths=new long[n+1];
  //boolean[] viss=new boolean[n+1];
  //viss[1]=true;
  //paths[1]=1;
  //
  //while (!queue.isEmpty()){
  //    int te=queue.poll();
  //
  //
  //    for(Integer v:linkedLists[te]){
  //        if(!viss[v]){
  //            viss[v]=true;
  //            queue.add(v);
  //        }
  //        if(vis[te]+1<vis[v]){
  //            vis[v]=vis[te]+1;
  //            paths[v]=paths[te];
  //        }else if(vis[v]==vis[te]+1){
  //            paths[v]=(long)((long)((long)paths[v]+(long)paths[te])%mod);
  //        }
  //
  //    }
  //}
  //        System.out.println(paths[n]);
  
  
  
  
  //    static long maxx(int ind,int ind1,String str,String s){
  //        if(ind>=s.length()){
  //            return 1l;
  //        }
  //        if(ind1>=str.length()){
  //            return 0l;
  //        }
  //        if(dp[ind][ind1]!=-1){
  //            return dp[ind][ind1];
  //        }
  //        if(str.charAt(ind1)==s.charAt(ind)){
  //           // list.add(ind1);
  //            dp[ind][ind1]=(long)((long)maxx(ind+1,ind1+1,str,s) )%(long)mod;
  //            //list.remove(list.size()-1);
  //            dp[ind][ind1]=(long)((long)dp[ind][ind1]+(long)maxx(ind,ind1+1,str,s) )%(long)mod;
  //            return dp[ind][ind1];
  //        }else{
  //            return dp[ind][ind1]=(long)(maxx(ind,ind1+1,str,s) )%(long)(mod);
  //        }
  //    }
  //    static long[][] dp;
  //    static long mod=(long)(Math.pow(10,9)+(long)7);
  //
  //    static class compp implements Comparator<int[]>{
  //        public int compare(int[] a,int[] b){
  //            return a[0]-b[0];
  //        }
  //    }
  //    static int[][][] dp;
  //    static int maxx(int ind,int tot,int tot1,String str){
  //        if(ind>=str.length()){
  //            return 0;
  //        }
  //        if(dp[ind][tot][tot1]!=-1){
  //            return dp[ind][tot][tot1];
  //        }
  //        if(ind%2==0){
  //            int t=0;
  //            int t1=0;
  //            for(int i=ind;i<str.length();i++){
  //                if(i%2==0 ){
  //                    t++;
  //                }else {
  //                    t1++;
  //                }
  //            }
  //            if(t+tot<tot1){
  //                return dp[ind][tot][tot1]=0;
  //            }
  //            if(t1+tot1<tot){
  //                return dp[ind][tot][tot1]=0;
  //            }
  //            if(str.charAt(ind)=='0'){
  //                return dp[ind][tot][tot1]=maxx(ind+1,tot,tot1,str)+1;
  //            }else if(str.charAt(ind)=='1'){
  //                return dp[ind][tot][tot1]=maxx(ind+1,tot+1,tot1,str)+1;
  //            }else{
  //                return dp[ind][tot][tot1]=Math.min(maxx(ind+1,tot,tot1,str)+1,maxx(ind+1,tot+1,tot1,str)+1);
  //            }
  //        }else{
  //            int t=0;
  //            int t1=0;
  //            for(int i=ind;i<str.length();i++){
  //                if(i%2==0 ){
  //                    t++;
  //                }else {
  //                    t1++;
  //                }
  //            }
  //            if(t+tot<tot1){
  //                return dp[ind][tot][tot1]=0;
  //            }
  //            if(t1+tot1<tot){
  //                return dp[ind][tot][tot1]=0;
  //            }
  //            if(str.charAt(ind)=='0'){
  //                return dp[ind][tot][tot1]=maxx(ind+1,tot,tot1,str)+1;
  //            }else if(str.charAt(ind)=='1'){
  //                return dp[ind][tot][tot1]=maxx(ind+1,tot,tot1+1,str)+1;
  //            }else{
  //                return dp[ind][tot][tot1]=Math.min(maxx(ind+1,tot,tot1+1,str)+1,maxx(ind+1,tot,tot1,str)+1);
  //            }
  //        }
  //    }
      static boolean ffa=false;
  //    static int maxx(int ind1,int ind2,int flag,String str,String t1){
  //        if(ind2>=t1.length()){
  //            ffa=true;
  //            return 1;
  //        }
  //        if(ind1<0 || ind1>=str.length()){
  //            return -1;
  //        }
  //        if(aaa[ind1][ind2][flag]!=0){
  //            return aaa[ind1][ind2][flag];
  //        }
  //        if( flag==0 && str.charAt(ind1)==t1.charAt(ind2) ){
  //            return aaa[ind1][ind2][flag]= Math.max( maxx(ind1+1,ind2+1,0,str,t1),maxx(ind1+1,ind2,0,str,t1) );
  //        }else if(flag==0 ){
  //            return aaa[ind1][ind2][flag]=Math.max( maxx(ind1+1,ind2,0,str,t1),maxx(ind1-1,ind2,1,str,t1) );
  //        }else if(flag==1) {
  //            return aaa[ind1][ind2][flag]=Math.max( maxx(),maxx() );
  //        }
  //    }
      static int[][][] aaa;
      static class comp2 implements Comparator<long[]>{
          @Override
          public int compare(long[] o1, long[] o2) {
              return Long.compare(o2[2],o1[2]);
          }
      }
  
  
  }
  
  
  
  
  
  
  
  
  
  
  
  