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.util.*; 

import java.util.Scanner; 

// Working program with FastReader  

import java.io.BufferedReader;  

import java.io.IOException;  

import java.io.InputStreamReader;  

import java.util.Scanner;  

import java.util.StringTokenizer; 

  

public class Solution { 
   
    private static final int INF = (int) 1e9;
    long in= (long)Math.pow(10,9)+7;
      
    public static void main(String[] args) {
               FastReader s=new FastReader();
                try
               {
                 int t=s.nextInt();
                 while(t-->0)
                 {
                     int a=s.nextInt();
                     int b=s.nextInt();
                       int ans=Math.min(a,Math.min(b,(a+b)/3));
                       System.out.println(ans);
                 }
                 }
                catch(Exception e)
                 {
                  
                  }
    } 

 static class T
     {
         int data;
         int count;
          public T(int x,int y) 
           {
               this.data=x;
                this.count=y;
           } 
     }

   static class compare implements Comparator<T>

      {
          public  int compare(T a, T b)
           {
                return a.data-b.data;
               }
        }

//static ArrayList<Integer> primeFactors(int N)		// O(sqrt(N) / ln sqrt(N))
//	{
//		ArrayList<Integer> factors = new ArrayList<Integer>();		//take abs(N) in case of -ve integers
//		int idx = 0, p = primes.get(idx);

//		while(1l*p * p <= N)
//		{
//			while(N % p == 0) { factors.add(p); N /= p; }
//			p = primes.get(++idx);
//		}

//		if(N != 1)						// last prime factor may be > sqrt(N)
//			factors.add(N);				// for integers whose largest prime factor has a power of 1
//		return factors;
//	}

  // public  static long lcm(long a2, long b2) {
//	return (a2*b2)/gcd(a2,b2);
	//}

   
 public static int countsetbit(int n) 
    { 
  
        // base case 
        if (n == 0) 
            return 0; 
  
        else
  
            // if last bit set add 1 else add 0 
            return (n & 1) + countsetbit(n >> 1); 
    }
            
         public static  int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public static  long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
       static boolean isPrime(int n) 
    { 
        // Corner cases 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
  
        // This is checked so that we can skip 
        // middle five numbers in below loop 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
  
        for (int i = 5; i * i <= n; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
  
        return true; 
    } 
   
    

static class FastReader  

    {  

        BufferedReader br;  

        StringTokenizer st;  

   

        public FastReader()  

        {  

            br = new BufferedReader(new 

                     InputStreamReader(System.in));  

        }  

   

        String next()  

        {  

            while (st == null || !st.hasMoreElements())  

            {  

                try 

                {  

                    st = new StringTokenizer(br.readLine());  

                }  

                catch (IOException  e)  

                {  

                    e.printStackTrace();  

                }  

            }  

            return st.nextToken();  

        }  

   

        int nextInt()  

        {  

            return Integer.parseInt(next());  

        }  

   

        long nextLong()  

        {  

            return Long.parseLong(next());  

        }  

   

        double nextDouble()  

        {  

            return Double.parseDouble(next());  

        }  

   

        String nextLine()  

        {  

            String str = "";  

            try 

            {  

                str = br.readLine();  

            }  

            catch (IOException e)  

            {  

                e.printStackTrace();  

            }  

            return str;  

        }  

    } 

    


  

} 