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.
def shovels(sticks, diamonds):
    ans = 0
    while sticks >= 2:
        sticks -= 2
        diamonds -= 1
        ans += 1

    return ans, sticks, diamonds

def swords(sticks, diamonds):
    ans = 0
    while diamonds >= 2:
        diamonds -= 2
        sticks -= 1
        ans += 1

    return ans, sticks, diamonds


def solve():

    [sticks, diamonds] = [int(x) for x in input().split()]

    if sticks == 0 or diamonds == 0:
        return 0

    if sticks <= diamonds:
        small = sticks
        big = diamonds
    else:
        big = sticks
        small = diamonds

    if small <= big // 2:
        return small
    
    return (small + big) // 3

    # ans = 0

    # while True:
    #     if sticks == 0 or diamonds == 0:
    #         return ans
        
    #     if sticks == 1 and diamonds == 1:
    #         return ans 

    #     if sticks > diamonds and sticks >= 2:
    #         sticks -= 2
    #         diamonds -= 1
    #         ans += 1
        
    #     if diamonds >= sticks and diamonds >= 2:
    #         diamonds -= 2
    #         sticks -= 1
    #         ans += 1

def main():
    t = int(input())
    while t > 0:
        ans = solve()
        print(ans)
        t -= 1

main()

'''
if sticks > diamonds:
        x, y = 0, 0
        x, sticksn, diamondsn = shovels(sticks, diamonds)

        if sticks >= 1:
            y, sticksn, diamondsn = swords(sticksn, diamondsn)

        return x + y

    x, y = 0, 0
    x, sticksn, diamondsn = swords(sticks, diamonds)

    if diamonds >= 1:
        y, sticksn, diamondsn = shovels(sticksn, diamondsn)

    return x + y
    '''