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.
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 18 12:33:18 2021

@author: Dave
"""

import sys
gDebug = 0

def readInt():
    global infile
    line = infile.readline()
    return int(line.strip())

def ignoreLine():
    global infile
    line = infile.readline()

def readIntList():
    global infile
    line = infile.readline()
    return [int(w) for w in line.split()]

# Setup input file

if len(sys.argv) > 1:
    infile = open(sys.argv[1], 'r')
else:
    infile = sys.stdin

# Read number of test cases
T = readInt()
        
# parse remaining lines
for t in range(T):
    V = readIntList()
    a = V[0]
    b = V[1]

    S = 0
    count = a
    A = []
    
    for n in range(a):
        S ^= n
        if gDebug:
            A.append(n)

    d = S ^ b

    if (gDebug):
        print(A)
        print(f'MEX = {a} XOR = {b} S = {S} diff = {d}')
        if S != b:
            print('Searching...')
            for i in range(a+1, 300000):
                if (S ^ i) == b:
                    A.append(i)
                    print('Append', i)
                    print(A)

    if d == 0:
        pass
    elif d > a:
        count += 1
    else:
        count += 2

    print(count)
                    
        
