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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main 
{
    static ArrayList<Integer> ar=new ArrayList<>();
    static long fAns;
    static long fact(long j)
    {
        if(j==1)
        return 1;
        return j*fact(j-1);
    }
    static int gcd(int a,int b)
    {
        if(a==0)
        return b;
        return gcd(b%a,a);
    }
    static void f1(long a,long b)
    {
        
        fAns+=b/a;
        if(b%a==0)
        return;
        
        
        if(b%a>0)
        f1(b%a,a);
        
    }
    static long noOfDivisors(long n)
    {
        long ans=0l;
        if(n%2==0)
        ans++;
        while(n%2==0)
        {
            n/=2;
        }
        
        for(int i=3;i<=Math.sqrt(n);i+=2)
        {
            if(n%i==0)
            {
                while(n%i==0)
                {
                    n/=i;
                }
                ans++;
            }
        }
        if(n>2)
        ans++;
        return ans;
    }
    static void seive()
    {
        int i,j;
        boolean a[]=new boolean[32001];
        for(i=2;i<=Math.sqrt(32000);i++)
        {
            for(j=i*i;j<=32000;j+=i)
            a[j]=true;
        }
        for(i=2;i<=32000;i++)
        if(!a[i])
        ar.add(i);
    }
	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		int T=fs.nextInt();
		int i,j,k;
		long n,m;
        // int T=1;
        long ans=0l,max=0l,a,b;
        // seive();
		for (int tt=0; tt<T; tt++) 
		{
			n=fs.nextLong();
			m=fs.nextLong();
// 			ans=fs.nextLong();
// 			max=fs.nextLong();
// 			int a[]=fs.readArray(n);
// 			Arrays.sort(a);
            ans=0l;
            if(m==0||n==0)
            {
                System.out.println(0);
                continue;
            }
            if(Math.max(m,n)>=2*Math.min(m,n))
            {
                System.out.println(Math.min(m,n));
                continue;
            }
            else
            {
                if(m!=n)
                {
                    a=Math.min(m,n);
                    b=Math.max(m,n);
                    long d=b-a;
                    if(m>n)
                    {
                       m-=2*d;
                    n-=d; 
                    }
                    else
                    {
                        n-=2*d;
                        m-=d;
                    }
                    ans+=d;
                }
                System.out.println(ans+(long)(2.0*Math.max(m,n)/3));
                
            }
            
		}
	}
 
	static final Random random=new Random();
	
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
 
	
}