Polycarp plays a well-known computer game (we won't mention its name). In this game, he can craft tools of two types — shovels and swords. To craft a shovel, Polycarp spends two sticks and one diamond; to craft a sword, Polycarp spends two diamonds and one stick.

Each tool can be sold for exactly one emerald. How many emeralds can Polycarp earn, if he has a sticks and b diamonds?

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

The only line of each test case contains two integers a and b (0 ≤ a, b ≤ 10^9) — the number of sticks and the number of diamonds, respectively.

Output

For each test case print one integer — the maximum number of emeralds Polycarp can earn.

Example

Input


4
4 4
1000000000 0
7 15
8 7


Output


2
0
7
5

Note

In the first test case Polycarp can earn two emeralds as follows: craft one sword and one shovel.

In the second test case Polycarp does not have any diamonds, so he cannot craft anything.
import sys
if sys.subversion[0] == "PyPy":
    import io, atexit
    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
    
    sys.stdin = io.BytesIO(sys.stdin.read())
    raw_input = lambda: sys.stdin.readline().rstrip()

RS = raw_input
RI = lambda : map(int,RS().split())
RN = lambda : int(RS())
''' ...................................................................... '''

def make(a,b):
    if a<b: a,b = b,a
    return max(0,min(a/2,b))

for _ in xrange(RN()):
    a,b = RI()
    if a<b: a,b = b,a

    if a>=2*b:
        print b
    else:
        mak = make(a,b)
        ans = mak
        for i in xrange(100):
            if i>=mak: break
            old = mak-i
            a_left = a-2*old
            b_left = b-old
            ans = max(ans,old+make(a_left,b_left))

        print ans
            
            
        
        
            
        

    
        
        
    

    

    
