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.
"""
ind=0
bal=True
a=0
top=''
S=str(input())
stack=[]
while(ind<len(S)):
    if(len(stack)==0):
        a=ind

    if(S[ind]=='[' or S[ind]=='{' or S[ind]=='('):
            stack.append(S[ind])
    else:
            if((S[ind]==']' or S[ind]=='}' or S[ind]==')')):
                if(len(stack)==0):
                    bal=False
                    break
                else:
                    top=stack[(len(stack)-1)]
                    stack.pop()
                    if((top=='[' and S[ind]!=']') or (top=='{' and S[ind]!='}') or (top=='(' and S[ind]!=')')):
                        bal=False
                        break
    ind=ind+1

if(bal and len(stack)==0):
    print("Success")
else:
    if(ind>=len(S) and len(stack)!=0):
        print(a+1)
    else:
        print(ind+1)"""

"""def binsrch(l,h,arr,x):
    mid=l+(h-l)//2
    if(h<l):
        return -1
    if(x==arr[mid]):
        return mid
    if(x>arr[mid]):
        return binsrch(mid+1,h,arr,x)
    else:
        return binsrch(l,mid-1,arr,x)




l=list(map(int,input().split()))
n=l[0]
a=l[1:n+1]


b=list(map(int,input().split()))



for i in range(1,len(b)):
    print(binsrch(0,n-1,a,b[i]),end=' ')
    r = 0
    le = n - 1
    ch=0
    while(r<=le):

        mid = r + (le - r) // 2;


        if a[mid] == b[i]:
            print(mid,end=' ')
            ch=1
            break


        elif a[mid] < b[i]:
            r = mid + 1


        else:
            le = mid - 1


    if(ch==0):
        print(-1, end=' ')
"""
"""def sftdn(i,arr):
    while(i<n):
        if (l[(2 * i) + 1] < l[(2 * i) + 2] and l[(2 * i) + 1] < l[i]):

            print(i, (2 * i) + 1)
            swap(l, i, (2 * i) + 1)

        elif (l[(2 * i) + 2] < l[(2 * i) + 1] and l[(2 * i) + 2] < l[i]):
            print(i, (2 * i) + 2)
            swap(l, i, (2 * i) + 2)
        elif (l[(2 * i) + 2] == l[(2 * i) + 1] and l[(2 * i) + 2] < l[i]):
            print(i, (2 * i) + 2)
            swap(l, i, (2 * i) + 2)
"""
"""ans=[]
def sftdn(i):

    minind=i
    li=(2*i)+1
    if(li<=n-1 and l[li]<l[minind]):
        minind=li
    ri=(2*i)+2
    if(ri<=n-1 and l[ri]<l[minind]):
        minind=ri
    if(i!=minind):
        swap(l,i,minind)
        ans.append(i)
        ans.append(minind)
        sftdn(minind)


def swap(arr,n1,n2):
    t=arr[n1]
    arr[n1]=arr[n2]
    arr[n2]=t



n=int(input())
ans=[]
l=list(map(int,input().split()))
for i in range (((n-1)//2),-1,-1):

    sftdn(i)"""






"""print(len(ans)//2)

for i in range(0,len(ans)-1,2):
    print(ans[i],ans[i+1])"""

t=int(input())
for tc in range(t):
    a,b=map(int,input().split())
    gr=max(a,b)
    lr=min(a,b)

    if(a!=0 and b!=0 ):
        if(gr/lr<=2):
         print((a+b)//3)
        else:
            print(lr)

    else:
        print(0)





