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.
/*Radhe Krishna*/
import javax.management.DynamicMBean;
import javax.print.DocFlavor;
import javax.print.attribute.HashAttributeSet;
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.net.CookieHandler;
import java.nio.file.attribute.FileAttribute;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;
import java.util.Arrays;
import java.util.concurrent.Callable;



public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

    public static void main(String[] args) {
        FastReader sc = new FastReader();
//        PrintWriter out = new PrintWriter(System.out);
       int t=sc.nextInt();
       for(int i=0;i<t;i++){
           int a=sc.nextInt();
           int b=sc.nextInt();
           if(a==0 || b==0){
               System.out.println(0);
               continue;
           }
           int min=Math.min(a,b);
           int max=Math.max(a,b);
          if(max>=2*min){
              System.out.println(min);
              continue;
          }
          int count=0;
          int val=(min/3);
          count+=val*2;
          max-=3*val;min-=3*val;int p=0,q=0;
          while(min>=1 && max>=2){
              p=min-1;
              q=max-2;
              min=Math.min(p,q);
              max=Math.min(p,q);
              count++;
          }
          System.out.println(count);
       }
    }
}


