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

public class SwordsAndShovels {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int t = Integer.parseInt(br.readLine());
		
		while(t-- > 0) {
			String[] nums = (br.readLine()).trim().split("\\s+");
			int a = Integer.parseInt(nums[0]);
			int b = Integer.parseInt(nums[1]);
			int cnt = 0;
			if(a == 0 || b == 0) {
				cnt = 0;
			} else {
				if(a > b) {
					int temp = a;
					
					a -= (temp-b)*2;
					if(a < 0) {
						cnt = b;
					} else {
						cnt += (temp - b);
					}
					b = a;
				} else if(b > a) {
					int temp = b;
					
					b -= (temp-a)*2;
					
					if(b < 0) {
						cnt += a;
					} else {
						cnt += (temp - a);
					}
					
					a = b;
				}
				if(a > 0 || b > 0) {
					cnt += 2*(a/3);
				}
			}
			bw.write(cnt + "\n");
		}
		bw.flush();
	}

}
