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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.*;
public class ShovelsAndSwords {

static long TIME_START, TIME_END;
static Scanner sc = new Scanner(System.in);
static PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
public static void main(String[] args) throws IOException {
	
	Runtime runtime = Runtime.getRuntime();
	long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
	TIME_START = System.currentTimeMillis();
	
	// code here..
	int t = sc.nextInt();
	while(t-->0) {
		sol();
	}
	TIME_END = System.currentTimeMillis();
	long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
	pw.close();
	System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
	System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
}
private static void sol() throws IOException{
	int a = sc.nextInt();
//	int cnt  =0;
	int b = sc.nextInt();
	if(a !=0 && b!=0) pw.println((a+b)/3);
	else pw.println("0");
}
static class Scanner {
	StringTokenizer st;
	BufferedReader br;
	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}
	public Scanner(FileReader s) throws FileNotFoundException {
		br = new BufferedReader(s);
	}
	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	public String nextLine() throws IOException {
		return br.readLine();
	}
	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	public boolean ready() throws IOException {
		return br.ready();
	}
}



}
