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.
c=[]
for i in range(int(input())):
    z = [int(X) for X in input().split()]
    a = z[0]
    b=z[1]
    
    em=0
    
    if a>b:
        d=a-b
        if b<=d:
            em+=b
        else:
            b-=d
            em+=d
            if b!=1:
                k=2*b
                em+=k//3
    
    elif b>a:
        d=b-a
        if a<=d:
            em+=a
        else:
            a-=d
            em+=d
            if a!=1:
                k=2*a
                em+=k//3

    else:
        if b!=1:
            em+=(2*b)//3

    
    c.append(em)
    
for i in c:
    print(i)
            