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.
t=int(input())
for i in range(t):
    #a = list(map(int,input().strip().split()))[:3]
    a,b = [int(item) for item in input().split()]
    
    # a1=no of sticks used and b1= no of diamonds used to craft to craft shovels, 
    #so no of shivels = b1 and a1=2*b1
    # a2=no of sticks used and b2= no of diamonds used to craft to craft swords, 
    #so no of shivels = a2 and b2=2*a2
    
    #this gives total no emeralds=shovels + swords = b1+a2
    #Also a1+a2<=a(total sticks) and b1+b2<=b(total diamonds)
    
    #if (2*a>b) and (2*b>a):
    if (2*a-b>0) and (2*b-a>0):
        #or out=b1+a2
        out=int((a+b)/3)
    else:
        out=min(a,b)
    print(out)