## Algorithm

B. MEXor Mixup
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice gave Bob two integers a and b (a>0�>0 and b0�≥0). Being a curious boy, Bob wrote down an array of non-negative integers with MEXMEX value of all elements equal to a and XORXOR value of all elements equal to b.

What is the shortest possible length of the array Bob wrote?

Recall that the MEXMEX (Minimum EXcluded) of an array is the minimum non-negative integer that does not belong to the array and the XORXOR of an array is the bitwise XOR of all the elements of the array.

Input

The input consists of multiple test cases. The first line contains an integer t (1t51041≤�≤5⋅104) — 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 (1a31051≤�≤3⋅1050b31050≤�≤3⋅105) — the MEXMEX and XORXOR of the array, respectively.

Output

For each test case, output one (positive) integer — the length of the shortest array with MEXMEX a and XORXOR b. We can show that such an array always exists.

Example
input
Copy
5
1 1
2 1
2 0
1 10000
2 10000

output
Copy
3
2
3
2
3

Note

In the first test case, one of the shortest arrays with MEXMEX 11 and XORXOR 11 is [0,2020,2021][0,2020,2021].

In the second test case, one of the shortest arrays with MEXMEX 22 and XORXOR 11 is [0,1][0,1].

It can be shown that these arrays are the shortest arrays possible.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
int res, n = a - 1;
if(n % 4 == 0){
res = n;
}
else if(n % 4 == 1){
res = 1;
}
else if(n % 4 == 2){
res = n + 1;
}
else{
res = 0;
}

if(res == b){
cout<<a<<endl;
}
else{
if((res ^ b) != a){
cout<<(a + 1)<<endl;
}
else{
cout<<(a + 2)<<endl;
}
}
}
}
Copy The Code &

Input

cmd
5
1 1
2 1
2 0
1 10000
2 10000

Output

cmd
3
2
3
2
3