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

import java.util.*;


public class Solve{
    static final int MOD=1000000007;
   
    public static void main (String[] args) throws Exception{
         BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
          PrintWriter out=new  PrintWriter(System.out,true);
        
       
          int t=Integer.parseInt(in.readLine());

        while(t-->0)
          solve(in,out);
       
    }

    private static void solve(BufferedReader in,PrintWriter out)throws Exception {
            String[] nk=in.readLine().trim().split(" ");
            int n=Integer.parseInt(nk[0]);
            int k=Integer.parseInt(nk[1]);

            if(n==0 || k==0) out.println(0);
           else if(k>2*n)
                out.println(n);
            else if(n>2*k) out.println(k);
            else{
                int s=n+k;
                out.println(s/3);
            }

      }

      private static long power(long n,long p,long m){
        
        long result=1;

        while(p>0){
            if(p%2==1) result=(result*n)%m;
            n=(n*n)%m;
            p>>=1;
        }
        return result;
    }

   private int gcd(int a, int b) {
        if(b==0)
            return a;
        else
            return gcd(b, a % b);
    }


    private static void sieve(int n){
         boolean[] prime=new boolean[n];
         for(int i=0;i<n;i++)
             prime[i]=true;
         for(int i=2;i*i<n;i++){
            if(prime[i]){
                for(int j=i*i;j<n;j+=i)
                 prime[j]=false;
            }
        }
         for ( int i = 2; i < prime.length; i++) {
             if(prime[i])
              System.out.print(i+" ");
         }  
         
    
    }

    private static void segmentedSieve(int low,int high){

        int sqrt=(int) Math.sqrt(high);
        int[] prime=new int[sqrt+1];
        boolean[] arr=new boolean[sqrt+1];

        for(int i=0;i<=sqrt;i++)
            arr[i]=true;

        int k=0;
        for(int i=2;i<=sqrt;i++){           //generate all prime numbers till square root of high
            if(arr[i]){
                prime[k]=i;
                
                k++;
                for (int j = i*i; j <= sqrt; j+=i) 
                    arr[j]=false;
        
                
             }
        }
        // System.out.println(Arrays.toString(prime));

        int diff=high-low+1;          // arr size of required length 
        arr=new boolean[diff];
        for(int i=0;i<diff;i++)
             arr[i]=true;
        
        for(int i=0;i<k;i++){               // mark false to multiple of prime numbers in the range of low to high
            int div=(low/prime[i])*prime[i];        // It gives multiple of prime[i] nearest to low 
            if(div<low || div==prime[i])
               div+=prime[i];
            for(int j=div;j<=high;j+=prime[i]){
                 if(j!=prime[i])
               arr[j-low]=false;
            }
        }
        for(int i=0;i<diff;i++){                //print prime numbers in the given segment
            if(arr[i] && (i+low)!=1){
                System.out.print(i+low+" ");
            }
        }
        System.out.println();

    }

    class Pair implements Comparable<Pair>{
        int a;
        int b;
        public Pair(int a,int b){
            this.a=a;
            this.b=b;
        }
    
        @Override
        public int compareTo(Pair o) {
          if(this.a>o.a) return this.a-o.a;
          else if(this.a<o.a)
              return this.b-o.b;
          
          else  return 0;
         
        }
    }
}
