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



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class vac {
	
	static void swap(int n, int m){
		int temp = n;
		n = m;
		m = temp;
		
		
	}
	static int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return 1; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
	
	static int Next_greater(int a[], int n, int x) 
	{ 
	  
	    // Sort the array 
	   
	
	    int low = 0, high = n - 1, ans = x + 1; 
	  
	    // Continue until low is less 
	    // than or equals to high 
	    while (low <= high) { 
	  
	        // Find mid 
	        int mid = (low + high) / 2; 
	  
	        // If element at mid is less than 
	        // or equals to searching element 
	        if (a[mid] <= ans) { 
	  
	            // If mid is equals 
	            // to searching element 
	            if (a[mid] == ans) { 
	  
	                // Increment searching element 
	                ans++; 
	  
	                // Make high as N - 1 
	                high = n - 1; 
	            } 
	  
	            // Make low as mid + 1 
	            low = mid + 1; 
	        } 
	  
	        // Make high as mid - 1 
	        else
	            high = mid - 1; 
	    } 
	  
	    // Return the next greater element 
	    return ans; 
	} 
	
	public static void main(String[] args) throws IOException{
		
		
		
		
			
			
			
			
		Reader.init(System.in);
		long t = Reader.nextLong();
		for(int i = 0;i<t;i++) {
			long a= Reader.nextLong();
			long b =Reader.nextLong();
			long c = 0;
			
			if(a==0||b==0) {
				System.out.println(0);
			}
			
			else if(a<=1 && b<=1) {
				System.out.println(0);
			}
			else {
			long max1 = Math.max(a, b);
			long min1 = Math.min(a, b);
			
			if(max1>= (2*min1)) {
				System.out.println(min1);
			}
			else {
				long q = Math.min(a, b);
				long q1 = Math.min(q, (a+b)/3);
				System.out.println(q1);
				
			
			
			
			
			
			}
			
			
				
			
		}
		
//			char x = 'Z';
//			char y = 'z';
//			int t = x;
//			int r = y;
//			System.out.println(t);
//			System.out.println(r);
//					
			
			
			
			
			
		
		
		
		
		
				
		
		
		
		
			
	
			
			
			
		
		
		
		
		
		
	
		}

	
		
//		Reader.init(System.in);
//		TreeSet<String> str = new TreeSet<String>(); 
//		
//			
//		int n = Reader.nextInt();
//		int m = Reader.nextInt();
//		String s1[] = new String[n];
//		
//		for(int j = 0;j<n;j++) {
//			String s = Reader.next();
//			str.add(s);
//			s1[j]=s;
//			
//		}
//		TreeSet<String> str2 = new TreeSet<String>(); 
//		
//		
//		for(int j = 0;j<n;j++)
//		{		
//			
//			StringBuilder a = new StringBuilder(s1[j]);
//			a.reverse();
//			String w = a.toString();
//			if(str.contains(w)&& !w.equals(s1[j])) {
//				StringBuilder a1 = new StringBuilder(s1[j]+w);
//				a1.reverse();
//				String f = a1.toString();
//				if(!str2.contains(w+s1[j])) {
//					str2.add(s1[j]+w);
//				}
//				}
//			}
//		
//		String a4 ="";
//		for(int j = 0;j<n;j++)
//		{		
//			
//			StringBuilder a = new StringBuilder(s1[j]);
//			a.reverse();
//			String d = a.toString();
//			if(d.equals(s1[j])) {
//				a4=s1[j];
//				break;
//				
//				
//			}
//				
//			}
//		String new1 = "";
//			
//		Iterator <String> it = str2.iterator();
//		while(it.hasNext()) {
//			new1+= it.next().substring(0,m);
//			
//		}
//		String new2 = "";
//		
//		Iterator <String> it2 = str2.descendingIterator();
//		while(it2.hasNext()) {
//			new2+= it2.next().substring(m,2*m);
//			
//		}
//		System.out.println((new1+a4+new2).length());
//		
//		System.out.println(new1+a4+new2);
		
		
		
		
		
		
				
				
	
			
			
		
		
			
			  
			
				
			
			
			
			
			
			
			
			
			
		
//			
			
		
	}
		

	    

}
	


class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

   
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

 
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
     
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
	
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
}

	