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.math.BigDecimal;
import java.util.*;

public class scratch_25 {
    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /** call this method to initialize reader for InputStream */
        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input) );
            tokenizer = new StringTokenizer("");
        }

        /** get next word */
        static String next() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                        reader.readLine() );
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble( next() );
        }
        static long nextLong() throws IOException{
            return Long.parseLong(next());
        }
    }
    static class pair
    {
        long first, second;
        public pair(long first, long second)
        {
            this.first = first;
            this.second = second;
        }
    }
    // To find the power of a prime p in
// factorial N
    static long findPowerOfP(long n, long p)
    {
        long count = 0;
        long r = p;
        while (n>0)
        {
            n/=r;

            // calculating Math.floor(n/r)
            // and adding to the count
            count += n ;

            // increasing the power of p
            // from 1 to 2 to 3 and so on

        }
        return count;
    }

    // returns all the prime factors of k

    // Returns largest power of k that
// divides n!
    static long largestPowerOfK(long n, long k)
    {
        Vector<pair > vec = new Vector<pair>();
        vec = primeFactorsofK(k);
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < vec.size(); i++){
          //  System.out.println("bhosdike");

            // calculating minimum power of all
            // the prime factors of k
            ans = Math.min(ans, findPowerOfP(n,
                    vec.get(i).first) / vec.get(i).second);}

        return ans;
    }
    public static Vector<pair> primeFactorsofK(long n)
    {
        Vector<pair> ans = new Vector<pair>();
        // Print the number of 2s that divide n
        long count=0;
        while (n%2==0)
        {
            count++;
           // System.out.print(2 + " ");
            n /= 2;
        }
        if(count>0){
        ans.add(new pair(2,count));}

        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            long count1=0;
            // While i divides n, print i and divide n
            while (n%i == 0)
            {
                count1++;
               // System.out.print(i + " ");
                n /= i;
            }
            if(count1>0){
            ans.add(new pair(i,count1));}
        }

        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if(n>2){
            ans.add(new pair(n,1));
        }
//

        return ans;
    }

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int t= Reader.nextInt();
        for (int i = 0; i <t ; i++) {
            long s = Reader.nextLong();
            long d= Reader.nextLong();
            if(s==d){
                if(s==0){
                    System.out.println(0);
                }
                else if(s==1){
                    System.out.println(0);
                }
                else if(s==2){
                    System.out.println(1);
                }
                else{
                if(s%2==0){
                    long count=0;
                    count+=(s-2)/2;
                    d-=count;
                    s-= (s-2);
                    if(d>3){
                        count+=2;
                    }
                    else{
                        count++;
                    }
                    System.out.println(count);
                }
                else if(s%2!=0){
                    long count=0;
                    count+=(s-1)/2;
                    d-=count;
                    s=1;
                    count+=1;
                    System.out.println(count);
                }
                }
            }
            else{
                long max = Math.max(s,d);
                long min= Math.min(s,d);
                if(max>=2*min){
                    System.out.println(min);
                }
                else{
                    long count=0;
                    if(max%2==0){
                        count+=(max-2)/2;
                        min-=count;
                        if(min>3){
                            count+=2;
                        }
                        else{
                            count+=1;
                        }
                        System.out.println(count);
                    }
                    else{
                        count+=(max-1)/2;
                       // count+=1;
                        min-=count;
                        if(min>1){
                            count+=1;
                        }
                        System.out.println(count);





                    }






                }















            }






        }


















      //  long u= (long)999999999989;
       // System.out.println();
































        }
//    static boolean isPrime(long 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 void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    static void sort(int arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
    static boolean ans(int check, long arr[],int n,int med,int k){
        long ans=0;
        for (int i = med; i <n ; i++) {
            if(check>=arr[i]){
                ans+=check-arr[i];
            }
        }
        return ans<=k;




    }

    static long smallestDivisor(long n)
    {
        // if divisible by 2
        if (n % 2 == 0)
            return 2;

        // iterate from 3 to sqrt(n)
        for (int i = 3; (long)i *(long) i <= n; i += 2) {
            if (n % i == 0)
                return i;
        }

        return n;
    }
    static boolean isPrime(long 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 (long i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }
static BigDecimal fd(int mid, double h, double c){
        BigDecimal a = new BigDecimal((h+c)/(2.0));
        BigDecimal b = new BigDecimal((h-c)/(2.0*mid));
        BigDecimal cd = a.add(b);
        return cd;




}
    static   int partition(double arr[],int arr1[],int arr2[], int low, int high)
    {
        double pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than the pivot
            if (arr[j] < pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                double temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                int temp1=arr1[i];
                arr1[i]=arr1[j];
                arr1[j]=temp1;
                int temp2=arr2[i];
                arr2[i]=arr2[j];
                arr2[j]=temp2;

            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        double temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
        int temp1= arr1[i+1];
        arr1[i+1]=arr1[high];
        arr1[high]= temp1;
        int temp2= arr2[i+1];
        arr2[i+1]=arr2[high];
        arr2[high]= temp2;

        return i+1;
    }


    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */
    static void sort(double arr[],int arr1[],int arr2[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr,arr1,arr2, low, high);

            // Recursively sort elements before
            // partition and after partition
            sort(arr,arr1,arr2, low, pi-1);
            sort(arr,arr1, arr2,pi+1, high);
        }
    }
    static int removeDuplicates(int arr[], int n)
    {
        // Return, if array is empty
        // or contains a single element
        if (n==0 || n==1)
            return n;

        int[] temp = new int[n];

        // Start traversing elements
        int j = 0;
        for (int i=0; i<n-1; i++)
            // If current element is not equal
            // to next element then store that
            // current element
            if (arr[i] != arr[i+1])
                temp[j++] = arr[i];

        // Store the last element as whether
        // it is unique or repeated, it hasn't
        // stored previously
        temp[j++] = arr[n-1];

        // Modify original array
        for (int i=0; i<j; i++)
            arr[i] = temp[i];

        return j;
    }
    static long maxPrimeFactors( long n)
    {
        // Initialize the maximum prime
        // factor variable with the
        // lowest one
        long maxPrime = -1;

        // Print the number of 2s
        // that divide n
        while (n % 2 == 0) {
            maxPrime = 2;

            // equivalent to n /= 2
            n >>= 1;
        }

        // n must be odd at this point,
        // thus skip the even numbers
        // and iterate only for odd
        // integers
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            while (n % i == 0) {
                maxPrime = i;
                n = n / i;
            }
        }

        // This condition is to handle
        // the case when n is a prime
        // number greater than 2
        if (n > 2)
            maxPrime = n;

        return maxPrime;
    }




}