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.math.BigInteger;
        import java.util.*;
        import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
    
    
        public class main2 {



    
            public static void main(String[] args) {
                try {
    
    
                    PrintWriter fop = new PrintWriter(System.out);
                    FastScanner fsca = new FastScanner();



                    int t = fsca.nextInt() ;
                    while (t-- > 0) {

                        long a = fsca.nextLong() ;
                        long b = fsca.nextLong() ;

                        System.out.println(Math.min(Math.min(a, b),(a+b)/3));


                    }



















                    fop.flush();
                    fop.close();
                } catch (Exception e) {
                    return;
                }
    
    
            }
            /*-----------------------------------------------------------------------------------------------------------------------------------------------*/
    
    
            static void sieve(int n) {
                boolean[] flag = new boolean[n];
    
                for (int i = 2; i * i < n; i++) {
                    if (flag[i])
                        continue;
                    else
                        for (int j = i * i; j <= n; j += i) {
                            flag[j] = true;
                        }
                }
            }
    
    
            static int gcd(int a, int b) {
                if (b > a) {
                    int tenp = b;
                    b = a;
                    a = tenp;
                }
                int temp = 0;
                while (b != 0) {
                    a %= b;
                    temp = b;
                    b = a;
                    a = temp;
                }
                return a;
            }
    
            static long gcd_long(long a, long b) {
                if (b > a) {
                    long tenp = b;
                    b = a;
                    a = tenp;
                }
                long temp = 0;
                while (b != 0) {
                    a %= b;
                    temp = b;
                    b = a;
                    a = temp;
                }
                return a;
            }
    
    
            static final Random random = new Random();
    
            static void ruffleSort(int[] a) {
                int n = a.length;//shuffle, then sort
                for (int i = 0; i < n; i++) {
                    int oi = random.nextInt(n), temp = a[oi];
                    a[oi] = a[i];
                    a[i] = temp;
                }
                Arrays.sort(a);
            }
    
    
            static class FastScanner {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st = new StringTokenizer("");
    
                String next() {
                    while (!st.hasMoreTokens())
                        try {
                            st = new StringTokenizer(br.readLine());
                        } catch (IOException e) {
                            e.printStackTrace();
                        }
                    return st.nextToken();
                }
    
                int nextInt() {
                    return Integer.parseInt(next());
                }
    
                int[] readArray(int n) {
                    int[] a = new int[n];
                    for (int i = 0; i < n; i++) a[i] = nextInt();
                    return a;
                }
    
                long[] readLongArray(int n) {
                    long[] a = new long[n];
                    for (int i = 0; i < n; i++)
                        a[i] = nextLong();
                    return a;
                }
    
                long nextLong() {
                    return Long.parseLong(next());
                }
            }
    
    
        }
    
    
    
    
    
    
    
    
