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 CfA {

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            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;
        }
    }

    static long binpow(int a, int b) {
        if (b == 0)
            return 1;
        long res = binpow(a, b / 2);
        if (b % 2 == 1)
            return res * res * a;
        else
            return res * res;
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static int n, m, x, y, k;
    static long ans;
    static final int MAX_K = 10000000;
    static int[] a,b;
    static Vertex[] a_sorted,a_unsorted;
    static List<Integer> freq;
    static HashSet<Integer> items_set = new HashSet<>();
    static int count2;

    static class Vertex implements Comparable<Vertex>
    { 
        int val;
        int index;
        int type;
        Vertex(int a,int b,int c)
        {
            val=a;
            type = b;
            index = c;
        }

        @Override 
        public int compareTo(Vertex o)
        {
            return this.val - o.val;
        }

        @Override
        public String toString() {
            // TODO Auto-generated method stub
            return val+"";
        }
    }


    public static void main(String[] args) throws Exception {
        Reader in = new Reader();
        int T = in.nextInt();
        while (T-- > 0) {       
            int inpa = in.nextInt();
            int inpb = in.nextInt();
            int a = Math.max(inpa,inpb);
            int b = Math.min(inpb,inpa);
            
            int ans = 0;
            int x = 1; 
            int count = 0;
            while(a > 0 && b > 0 && x != 0)
            {
                x = 2*a - b;
                x /= 3;
                if(x != 0)
                    count+=x;
                int tempa = a - 2*x;
                int tempb = b -x;
                a = Math.max(tempa,tempb);
                b = Math.min(tempa,tempb);
                // System.out.println("x = "+x+" a = "+a+" b = "+b);
            }

            System.out.println(count);


        }

    }


}

// 76 52 28 00 73 42 23 64 48