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 fun(x,y):
    a=0
    b=0
    if x>y:
        a = x
        b = y
    if x==y:
        a=x
        b = x
    if x<y:
        a=y
        b =x
    # print(a>=b)


    if a>=2*b:
        return b
    if a<2*b and a>b:

            return int((a+b)/3)


    if a==b:
        if a%3==1:
            return int((a+2)*2/3)-2
        if a%3==2:
            return int((a+1)*2/3)-1
        if a%3 == 0:
            return int((a)*2/3)

n = int(input())
lst = []
for _ in range(n):
    x,y = map(int,input().split())
    lst.append(fun(x,y))

for val in lst:
    print(val)