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.FileReader;
					import java.io.IOException;
					import java.io.InputStreamReader;
					import java.io.PrintWriter;
			import java.lang.reflect.Array;
			import java.math.BigInteger;
					import java.util.*;
		
						 public class Codeforces{
							  private static long [] catalan= new long[2501];
							  private static final int MOD=1000000007;


							    void pre() throws Exception{}
							    void solve(int TC) throws Exception{ 
							    	int t=ni();
							    	while(t--!=0) {
							    		int a =ni();
							    		int b=ni();
							    		int max=Math.max(a,b);
							    		int min=Math.min(a,b);
							    		int ans=Math.min(min,max/2);
							    		int dif=max-min;
							    		if(dif%2!=0&&min!=0)ans++;
							    		pn(ans);
							    	}
							   
							        }
							    

							    				
							    
			
							    static boolean multipleTC = false, memory = false;
							    FastReader in;PrintWriter out;
							    void run() throws Exception{
							        in = new FastReader();
							        out = new PrintWriter(System.out);
							        int T = (multipleTC)?ni():1;
							        pre();for(int t = 1; t<= T; t++)solve(t);
							        out.flush();
							        out.close();
							    }
							    public static void main(String[] args) throws Exception{
							        if(memory)new Thread(null, new Runnable() {public void run(){try{new Codeforces().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
							        else new Codeforces().run();
							    }
							    void p(Object o){out.print(o);}
							    void pn(Object o){out.println(o);}
							    void nd(Object o){out.println(o);}
							    void pni(Object o){out.println(o);out.flush();}
							    String n()throws Exception{return in.next();}
							    String nln()throws Exception{return in.nextLine();}
							    int ni()throws Exception{return Integer.parseInt(in.next());}
							    long nl()throws Exception{return Long.parseLong(in.next());}
							    double nd()throws Exception{return Double.parseDouble(in.next());}
							    
							    class FastReader{
							        BufferedReader br;
							        StringTokenizer st;
							        public FastReader(){
							            br = new BufferedReader(new InputStreamReader(System.in));
							        }
							
							        public FastReader(String s) throws Exception{
							            br = new BufferedReader(new FileReader(s));
							        }
							
							        String next() throws Exception{
							            while (st == null || !st.hasMoreElements()){
							                try{
							                    st = new StringTokenizer(br.readLine());
							                }catch (IOException  e){
							                    throw new Exception(e.toString());
							                }
							            }
							            return st.nextToken();
							        }
							
							        String nextLine() throws Exception{
							            String str = "";
							            try{   
								                str = br.readLine();
								            }catch (IOException e){
							                throw new Exception(e.toString());
							            }  
							            return str;
							        }
							    }
							}