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.
"""
from functools import reduce
import statistics
import numpy as np
import itertools
import statistics
import operator
import decimal
sys.setrecursionlimit(10 ** 6 + 1)
MAX = sys.maxsize
"""
# from time import time
# import math
import os
import sys
# from math import *
from io import BytesIO, IOBase
# from collections import *
from bisect import bisect_right, insort_right
BUFSIZE = 8192
import array


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
getint = lambda: int(sys.stdin.readline().rstrip("\r\n"))
getints = lambda: map(int, sys.stdin.readline().rstrip("\r\n").split())
lgetints = lambda: list(map(int, sys.stdin.readline().rstrip("\r\n").split()))
getstrs = lambda: map(str, sys.stdin.readline().rstrip("\r\n").split())

# def gcd(a, b):
#     if a == 0:
#         return b
#     else:
#         return gcd(b % a, a)

# def fact(num):
#     # cnt = 0
#     for x in range(2, int(sqrt(num)) + 1):
#             # if num // x == x:
#                 # cnt += 1
#             # else:
#                 # cnt += 2
#     # return cnt

# def isPrime(num):
#     if num == 2:
#         return True
#     elif num % 2 == 0:
#         return False
#     else:
#         i = 3
#         while i * i <= num:
#             if num % i == 0:
#                 return False
#             i += 2
#         return True

# def power(x, y, m):
#     res = 1
#     x = x % m
#     while y > 0:
#         if y & 1:
#             res = res * x % m
#         x = x * x % m
#         y = y >> 1
#     return res

def prog_name():
    a, b = getints()
    x = 0
    n = a - 1
    if n % 4 == 0:
        x = n
    elif n % 4 == 1:
        x = 1
    elif n % 4 == 2:
        x = n + 1
    else:
        x = 0

    ans = b ^ x

    if x == b:
        print(a)
    else:
        if ans == a:
            print(a + 2)
        else:
            print(a + 1)




# print()
def main ():
    # init = time()
    T = getint()
    for unique in range(T):
        # print("Case #"+str(unique+1)+":", end = " ")
        # print()
        prog_name()
    # print(time() - init)


if __name__ == "__main__":
    main()