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.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

#define int long long
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k-1)  returns iterator to kth element starting from 0; Returns the kth smallest element
// order_of_key(k) returns count of elements strictly smaller than k;Returns the number of elements less than k
// erase,insert same as normal set, CAREFUL it does not behave as multiset for it use pii
// USE PRE_SUM FOR RANGE CALCULATIONS TO AVOID TLE
// agr kisi ko soch nhi pa rhe toh socho ki agr yeh ho gaya toh kaisa ho.
// agr TLE aa rha h toh global vectors ko clear karke dhekho.

void solve() {
	int a,b;
	cin>>a>>b;
	int cnt=0;
	for(int i=0;i<1000;i++){
		if(a>b && a>=2 && b>=1){
			int rem=min({a/2,b,(a-b)});
			cnt+=rem;
			a-=2*rem;
			b-=rem;
		}
		else if(b>a && b>=2 && a>=1){
			int rem=min({a,b/2,(b-a)});
			cnt+=rem;
			b-=2*rem;
			b-=rem;
		}
		else if(a==b && a>=2){
			int rem=a/3;
			cnt+=2*rem;
			a-=3*rem;
			b-=3*rem;
		}
		// cerr<<"a:"<<a<<" :b"<<b<<" :c"<<cnt<<endl;
	}

	cout<<cnt<<endl;
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	if(fopen("input.txt", "r")){
	    freopen("input.txt", "r", stdin),
	    freopen("output.txt", "w", stdout);
	}
	
	int t = 1;
	cin>>t;
	while (t--) {
		solve();
	}
}