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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class d extends PrintWriter{
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    // static Scanner s=new Scanner(System.in);
    d() { super(System.out); }
    public static void main(String[] args) throws IOException{
        d d1=new d();d1.main();d1.flush();
    }void main() throws IOException {
        //        StringBuilder sb = new StringBuilder();
        PrintWriter out = new PrintWriter(System.out);
        String[] s1=s();
        int t=i(s1[0]);
        while(t-->0){
            String[] s2=s();
            int a=i(s2[0]);
            int b=i(s2[1]);
            int x=Math.min(a,b);
            int z=Math.max(a,b);
            int ans=0;
            while(z>0&&x>0){
                if(x>z){
                    int temp=z;z=x;x=temp;
                }
            if(z-x==0){
                ans+=(z/3*2);break;
            }
            else if(z-x==1){
                ans+=(z/3*2);
                z%=3;x%=3;
                if(z+x==3) ans++;break;
            }else{
                int z1=Math.min((z-x)/2,x);
               ans+=z1;
                z-=z1*2;
                  x-=z1;
                }
            }
            System.out.println(ans);
        }
    }
    static String[] s() throws IOException {

        return s.readLine().trim().split("\\s+");
    }

    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
}
class node implements Comparator<node>{
    int ver,val;
    public node(){}
    public node(int ver,int val) {
        this.ver=ver;this.val=val;
    }public int compare(node n1,node n2){
        return n1.val-n2.val;
    }
}

class Student12 {
    int  l;int r;
    public Student12(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public String toString()
    {
        return this.l+" ";
    }
}
class Sortbyroll12 implements Comparator<Student12> {

    public int compare(Student12 a, Student12 b){
        return a.l-b.l;
        //        if(a.r<b.r) return 1;else if(a.r==b.r) return 0;else return -1;// a.r-b.r;
          /*  if(b.r<a.r) return -1;
            else if(b.r==a.r) return 0;
            return 1;*/

        //   return b.r-a.r;
           /*
           if(b.l<a.l) return -1;
           else if(b.l==a.l) {
               return b.r-a.r;
           }
           return 1;*/
        //        return b.r- a.r;
        //        return (int) a.l-(int) b.l;
             /*   if(a.r<b.r) return -1;
                else if(a.r==b.r){
                    if(a.r==b.r){
                        return 0;
                    }
                    if(a.r<b.r) return -1;
                    return 1;}
                return 1;  */}
}
class Node1 implements Comparator<Node1>{
    int node;long val;
    public  Node1(){}
    public  Node1(int node,long val){
        this.node=node;this.val=val;
    }
    @Override
    public int compare(Node1 a,Node1 b){
        if(a.val<b.val) return -1;
        if(a.val==b.val) return 0;
        {
            return 1;
        }
    }
}