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.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class A {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static PrintWriter out = new PrintWriter(System.out);

	static void solve() throws Exception {
		int t = nextInt();
		for (int i = 0; i < t; i++) {
			long a = nextLong(), b = nextLong();
			long max = Math.max(a, b), min = Math.min(a, b);
			long r = 0;
			long dif = max - min;
			long first;
//			System.out.println(max);
//			System.out.println(min);
//			System.out.println(dif);
			if (dif > min) {
				first = min;
			} else {
				first = dif;
			}
			r += first;
			max -= (2 * first);
			min -= first;

			if (max >= 3 && min >= 3) {
				long maxi = Math.max(max, min), mini = Math.min(max, min);
				long div = mini / 3;
				max = maxi - div * 3;
				min = mini - div * 3;
				r += div * 2;
			}
			while ((min >= 2 && max >= 1) || (max >= 2 && min >= 1)) {
				long maxi = Math.max(max, min), mini = Math.min(max, min);
				max = maxi - 2;
				min = mini - 1;
				r += 1;
			}
////			System.out.println(max);
//			System.out.println(min);
//			System.out.println(dif);

			out.println(r);
		}
	}

	public static void main(String[] args) throws Exception {
		solve();
		out.close();
	}

	static String next() throws Exception {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(br.readLine());
		}
		return st.nextToken();
	}

	static int nextInt() throws Exception {
		return Integer.parseInt(next());
	}

	static long nextLong() throws Exception {
		return Long.parseLong(next());
	}
}
