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.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.text.DecimalFormat;
import java.lang.Math;
import java.util.Iterator; 
import java.util.TreeSet;
public class A1366{
    static int pInf = Integer.MAX_VALUE;
    static int nInf = Integer.MIN_VALUE;
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0){
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    int max = Math.max(a,b);
		    int min = Math.min(a,b);
		    if(min< max/2){
		        System.out.println(min);
		    }
		    else{
		        System.out.println((min+max)/3);
		    }
		}
	}
	public static int ffloor(int[] b, long ele){
	    int s = 0;
	    int e = b.length-1;
	    while(s<=e){
	        int m = s+(e-s)/2;
	        if(b[m] == ele){
	            return b[m];
	        }
	        else if(b[m]>ele){
	            e = m-1;
	        }
	        else{
	            s = m+1;
	        }
	    }
	    return b[e];
	}
	public static int cceil(int[] a, long ele){
	    int s = 0;
	    int e = a.length-1;
	    while(s<=e){
	        int m = s+(e-s)/2;
	        if(a[m] == ele){
	            return a[m];
	        }
	        else if(a[m]>ele){
	            e = m-1;
	        }
	        else{
	            s = m+1;
	        }
	    }
	    return a[s];
	}
	public static int floor(ArrayList<Pair> A , long ele){
	    int s = 0;
	    int e = A.size()-1;
	    while(s<=e){
	        int m = s+(e-s)/2;
	        if(A.get(m).x == ele){
	            return A.get(m).x;
	        }
	        else if(A.get(m).x>ele){
	            e = m-1;
	        }
	        else{
	            s = m+1;
	        }
	    }
	    return A.get(e).x;
	}
	public static int ceil(Pair[] a, long ele){
	    int s = 0;
	    int e = a.length-1;
	    while(s<=e){
	        int m = s+(e-s)/2;
	        if(a[m].x == ele){
	            a[m].y = 1;
	            return a[m].x;
	        }
	        else if(a[m].x>ele){
	            e = m-1;
	        }
	        else{
	            s = m+1;
	        }
	    }
	    a[s].y = 1;
	    return a[s].x;
	}
	////////////////////////////////////////////////////////////////////////////////
	static class Pair implements Comparable<Pair>{
		int x;
		int y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			if(this.x==o.x){
			    return (this.y-o.y);
			}
			return (this.x-o.x);
		}
	}
	public static boolean isPrime(int n){
	    if(n < 2){
	        return false;
	    }
	    if(n%2==0){
	        return n==2;
	    }
	    if(n%3==0){
	        return n==3;
	    }
	    int i = 5;
	    int h = (int)Math.floor(Math.sqrt(n)+1);
	    while(i <= h){
	        if(n%i==0){
	            return false;
	        }
	        if(n%(i+2)==0){
	            return false;
	        }
	        i += 6;
	    }
	    return true;
	}
	public static long gcd(long a, long b){
	    return b==0? a:gcd(b, a%b);
	}
	public static long bSearch(int n,ArrayList<Long> A){
	    int s = 0;
	    int e = A.size()-1;
	    while(s<=e){
	        int m = s+(e-s)/2;
	        if(A.get(m)==(long)n){
	            return A.get(m);
	        }
	        else if(A.get(m)>(long)n){
	            e = m-1;
	        }
	        else{
	            s = m+1;
	        }
	    }
	    return A.get(s);
	}
	static class Point implements Comparable<Point>{
		int x;
		int y;
		public Point(int x, int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(Point o) {
			// TODO Auto-generated method stub
			if(this.x==o.x){
			    return this.y-o.y;
			}
			return this.x-o.x;
		}
	}
	public static long[] fact;
	public static final long modulo = 1000000007;
	public static long modinv(long x){
	    return modpow(x, modulo-2);
	}
	public static long modpow(long a, long b){
	    if(b==0){
	        return 1;
	    }
	    long x = modpow(a, b/2);
	    x = (x*x)%modulo;
	    if(b%2==1){
	        return (x*a)%modulo;
	    }
	    return x;
	}
}