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 Main {
    static BufferedReader br;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc= 1;
        tc =cinI();


        while(tc-->0){
            String[] arr =cinA();
            long a  =getL(arr[0]);
            long b  =getL(arr[1]);
            long a1 = Math.max(a,b);
            long b1= Math.min(a,b);
            if(a1==0 || b1==0){
                System.out.println(0);
                continue;
            }
            if(a1/b1!=1){
                System.out.println(b1);
                continue;
            }
            if(a!=0 && b!=0){
                long sum  =(a+b)/3;
                System.out.println(sum);
                continue;
            }
            System.out.println(0);
        }


    }


    public static int binary(long val,long[] arr){
        //    System.out.println("value "+ val);
        int i=0;
        int mid= 0;
        int e = arr.length;
        while(i<=e){
            //    System.out.println(i+ " "+e);

            mid = (i+e)/2;

            if(arr[mid]==val){

                return mid;
            }
            if(arr[mid]>val){

                e=mid-1;
                continue;
            }
            i=mid+1;

        }
        // System.out.println(mid);
        return mid;
    }




    public static void arrinit(String[] a,long[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Long.parseLong(a[i]);
        }
    }
    public static void arrinit(String[] a,int[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }
    public static String[] cinA(int x) throws Exception{
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}

class range {
    int l;
    int r;
    int diff;

    public range(int l, int r, int diff) {
        this.l = l;
        this.r = r;
        this.diff = diff;
    }
}

class sortRange implements Comparator<range> {


    @Override
    public int compare(range range, range t1) {
        if (range.diff != t1.diff)
            return t1.diff - range.diff;
        return range.l - t1.l;

    }}