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.
################om namh shivay##################37
###############(BHOLE KI FAUJ KREGI MAUJ)############37
from sys import stdin,stdout 
import math,queue,heapq
fastinput=stdin.readline
fastout=stdout.write
t=int(fastinput())
while t:
    t-=1 
    #n=int(fastinput()) 
    n,m=map(int,fastinput().split())  
    #a=[0]+list(map(int,fastinput().split()))
    #b=list(map(int,fastinput().split()))
    #matrix=[list(map(int,fastinput().split())) for _ in range(n)] 
    n,m=min(n,m),max(n,m) 
    r=m-n 
    if r>=n:
        print(n)
    else: 
        m-=r
        print(r+ (2*m)//3)
    
        
            
    
    

    