human
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.
The above is tricky. Write me a correct solution in PYTHON3.
 ... Give me a the shortest possible length of the array Bob wrote?
assistant
#Here is the shortest possible length of the array Bob wrote.

import math, os, io, heapq
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

# For fast i/o
# def inp():
#     return io.BytesIO(os.read(0,os.fstat(0).st_size)).readline().strip().decode()
# input = inp

# def println(v, end='\n'):
#     stdout.write(str(v) + end)

def getList(method=int):
    return list(map(method, input().split()))

def getInt():
    return int(input())

def getXor(n):
    r = n % 4
    if r == 0:
        return n
    if r == 1:
        return 1
    if r == 2:
        return n + 1
    return 0

def solve():
    a, b = getList()
    x = getXor(a - 1)

    if x == b:
        return a

    if b ^ x != a:
        return a + 1

    return a + 2

for _ in range(getInt()):
    print(solve())

# x = 0
# for i in range(20):
#     x ^= i
#     print(x)