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.LinkedList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter out=new PrintWriter(System.out);
		
		int test = sc.nextInt();
		while(test-->0)
		{
		    int a = sc.nextInt();
		    int b = sc.nextInt();
    // 		int []arr = new int[n];
    // 		for(int i=0;i<n;i++)
    // 		   arr[i] = sc.nextInt();
    		   
    	    int ans = Math.min(Math.min(a, b), (a+b)/3);	
    	    System.out.println(ans);
		}
		    
		out.close();
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
 
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}
 
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
 
		public int nextInt() {return Integer.parseInt(next());}
 
		public long nextLong() {return Long.parseLong(next());}
 
		public double nextDouble() {return Double.parseDouble(next());}
 
		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}
}
 
 