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 inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) ]))
def invr():
    return(map(int,input().split()))

entries = inp()

for i in range(entries):
    l = inlt()

    x = l[0]
    y = l[1]
    res = 0
    if(x > y):
        p = x - y
        x -= 2 * p
        if(y - p <= 0):

            print(y)
        else:
            res += p
            y = y - p
            res += x // 3 * 2
            y  = y % 3
            if(y == 2):
                res += 1
            print(res)
    else:
        p = y - x
        y -= 2 * p
        if(x - p <= 0):

            print(x)
        else:
            res += p
            x = x - p
            res += x // 3 * 2
            x = x % 3
            #print(x)
            if(x == 2):
                res += 1

            print(res)
