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 solve(a,b,data=None):
#     #setting up the data array if not done
#     if data == None:
#         if a == 0 or b == 0:
#             return 0
#         data = []
#         for i in range(a+1):
#             temp = []
#             for j in range(b+1):
#                 temp.append(None)
#             data.append(temp)
#
#         #Hardcoding initial values
#         for i in range(a):
#             data[i][0] = 0
#
#         for i in range(b):
#             data[0][i] = 0
#
#         data[1][1] = 0
#         data[2][1] = 1
#         data[1][2] = 1
#
#     #if the current data point has a value return it
#     if data[a][b] != None:
#         return data[a][b]
#
#     if a < 0 or b < 0:
#         return 0
#     if a-1 == b-2:
#         val = solve(a-1,b-2,data)+1
#     else:
#         val1 = solve(a-1,b-2,data)+1
#         val2 = solve(a-2,b-1,data)+1
#         val = max(val1,val2)
#
#     data[a][b] = val
#     print(data)
#     return data[a][b]

def solve(a,b):
    if a < b:
        a,b = b, a
    x = min(a//2,b)
    a -= 2*x
    b -= x
    e = x

    y = min(a,b//2)
    a -= y
    b -= 2*y
    e += y

    if b <= 1:
        return e
    else:
        z = b//3
        e += z
        return e

#
#

input()
while True:
    try:
        val = input().split(" ")
        for i in range(len(val)):
            val[i] = int(val[i])
        print(solve(val[0],val[1]))
    except EOFError:
        break