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>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
mt19937_64 rang(
    chrono::high_resolution_clock::now().time_since_epoch().count());
long long int toint(const string &s) {
  stringstream ss;
  ss << s;
  long long int x;
  ss >> x;
  return x;
}
string tostring(long long int number) {
  stringstream ss;
  ss << number;
  return ss.str();
}
template <typename T>
T toIntegralType(const string &str) {
  static_assert(is_integral<T>::value, "Integral type required.");
  T ret;
  stringstream ss(str);
  ss >> ret;
  if (to_string(ret) != str) throw invalid_argument("Can't convert " + str);
  return ret;
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second < b.second);
}
bool sortbysecdesc(const pair<int, int> &a, const pair<int, int> &b) {
  return a.second > b.second;
}
long long int fast_power(long long int a, long long int x) {
  if (x == 0)
    return 1;
  else if (x == 1)
    return a;
  else {
    long long int R = fast_power(a, x >> 1);
    if (!(x & 1))
      return R * R;
    else
      return R * a * R;
  }
}
void solve() {
  int a, b;
  cin >> a >> b;
  if (max(a, b) > 2 * min(a, b)) {
    cout << min(a, b);
  } else
    cout << (a + b) / 3;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
    cout << '\n';
  }
}
