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
input = sys.stdin.readline

'''
shovel = 2 sticks +1 diamond
sword = 2 diamond + 1 stick

'''

def calc_items(num_shovels, sticks, diamonds):
    if num_shovels * 2 < sticks or num_shovels < diamonds:
        return 

def get_shovels(sticks, diamonds):
    return min(sticks // 2, diamonds)

def get_swords(sticks, diamonds):
    return min(sticks, diamonds//2)


def solve(sticks, diamonds):
    # Greedy
    num_shovels = get_shovels(sticks, diamonds)
    num_swords = get_swords(sticks, diamonds)

    a1 = num_shovels + get_swords(sticks - num_shovels * 2, diamonds-num_shovels)
    a2 = num_swords + get_shovels(sticks - num_swords, diamonds - num_swords * 2)
    # One less of each

    a3 = 0
    if num_shovels > 0:
        num_shovels -= 1
        a3 = num_shovels + get_swords(sticks - num_shovels * 2, diamonds-num_shovels)

    a4 = 0
    if num_swords > 0:
        num_swords -= 1
        a4 = num_swords + get_shovels(sticks - num_swords, diamonds - num_swords * 2)

    return max(a1, a2, a3, a4)
"""    
def solve(sticks, diamonds):
    # shovel first
     = min(sticks // 2, diamonds)
    a1 = a1 + min(sticks - a1*2, (diamonds-a1) // 2)
    # sword first
    a2 = min(sticks, diamonds// 2)
    a2 = a2 + min((sticks - a2)//2 , diamonds-(a2*2))

    a3 = 0
    if sticks >= 2:
        a3 = min((sticks-2)//2, diamonds)
        a3 = a3 + min(sticks - )

    

    


    return max(a1, a2)

def solve(sticks, diamonds):
    if sticks <= 2 or diamonds <= 2:
        return max(min(sticks//2, diamonds), min(sticks, diamonds//2))
    elif sticks > diamonds:
        a1_shovel = min(sticks // 2, diamonds)
        a1_rest = solve(sticks - (a1_shovel * 2), diamonds - a1_shovel)
        a2 = 0
        if a1_shovel > 0:
            sticks_leftover = sticks -(sticks-2)//2
            a2 = min(sticks)


"""
t = int(input())
for _ in range(t):
    sticks, diamonds = map(int, input().split())
    print(solve(sticks, diamonds))
