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.io.*;

public class ShovelsandSwords {

	// https://codeforces.com/contest/1366/problem/A
	
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("ShovelsandSwords"));

		int t = Integer.parseInt(in.readLine());  
		for (int j=0; j<t; j++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			long a = Long.parseLong(st.nextToken()); 
			long b = Long.parseLong(st.nextToken()); 
			long total = 0;
			boolean done = false;
			if (a >b) {
				long needed = a-b;
				if (needed > b) {
					total += b;
					done = true;
				}
				else {
					total += needed;
					b -= needed;
					a -= 2*needed;
				}
			}
			else if (b > a) {
				long needed = b-a;
				if (needed > a) {
					total += a;
					done = true;
				}
				else {
					total += needed;
					a -= needed;
					b -= 2*needed;
				}
			}
			// b==a
			if (!done) {
				long needed = a/3;
				a %= 3;
				b %=3;
				total += 2*needed;
				
				if (a == 2 && b >= 1) {
					a -= 2;
					b -= 1;
					total++;
				}
				else if (b == 2 && a >= 1) {
					total++;
				}
				
			}
			System.out.println(total);
		}
	}
}

/* 

	while (a != b && a > 0 && b >0) {
		if (a > b) {
			a -= 2;
			b -= 1;
			total++;
		}
		else {
			b-=2;
			a--;
			total++;
		}
	}
	while (a >= 3 && b >= 3) {
		a -= 3;
		b -= 3;
		total += 2;
	}
	if (a == 2 && b >= 1) {
		a -= 2;
		b -= 1;
		total++;
	}
	else if (b == 2 && a >= 1) {
		total++;
	}
	System.out.println(total);
*/