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

public class Solution {
	public static void main(String[] args) throws IOException{
		FastScanner sc = new FastScanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = sc.nextInt();
		while (t-->0) {
			long a = sc.nextLong(), b = sc.nextLong();
			if(a>b){
				long temp = a;
				a = b;b = temp;
			}
			if (b>=2*a) {
				bw.write(a+"\n");
				continue;
			}
			long ans = 0;
			while (a>=3) {
				long temp = a/3;
				ans+=temp;
				a-=temp;
				b-=(2*temp);
				if(a>b){
					long temp2 = a;
					a = b; b = temp2;
				}
			}
			if (a==0) {
				bw.write(ans+"\n");
				continue;
			}
			if (a==1) {
				if(b>=2) ans++;
				bw.write(ans+"\n");
				continue;
			}
			if (b>=1 && b<=3) {
				ans++;
			}
			if(b>=4) ans+=2;
			bw.write(ans+"\n");
		}
		bw.close();
	}
	static class Pair implements Comparable<Pair>{
		int a;
		int b;
		public Pair(int c, int d){
			a = c;
			b = d;
		}
		public int compareTo(Pair p){
			return (int)(a-p.a);
		}
	}
	static int gcd(int a, int b){
	    if(b==0) return a;
	    return gcd(b,a%b);
	}
	static long power(long a, long b, long c){
	    if(b==0) return 1L;
	    if(b==1) return a;
	    long temp = power(a, b/2, c);
	    if(b%2==0) return (temp*temp)%c;
	    else return (((temp*temp)%c)*a)%c;
	}
	static long power(long a, long b){
	    if(b==0) return 1L;
	    if(b==1) return a;
	    long temp = power(a, b/2);
	    if(b%2==0) return (temp*temp);
	    else return (temp*temp*a);
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}
		FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}
		String nextLine() {
			try {
				return br.readLine();
			} catch (IOException e) {
				return null;
			}
		}
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}