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>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
void err(istream_iterator<string> it) { cout << '\n'; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << "[" << *it << " = " << a << "] ";
  err(++it, args...);
}
pair<int, int> dx[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int inf = 2e9 + 7;
const long long INF = 3e18 + 7;
const long double pi = 3.1415926535897932384626433;
const long double EPS = 1e-9;
const int mod = 1e9 + 7;
long long MOD = 1e15 + 7;
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
const bool multiple_tests = 1;
const long long N = 2e5 + 7;
void solve() {
  long long a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);
  long long del = min(b - a, min(a, b / 2));
  a -= del;
  b -= del * 2;
  long long ans = del + ((a / 3) * 2);
  if (a > b) swap(a, b);
  b -= (a / 3) * 3;
  a -= (a / 3) * 3;
  while (a >= 0 && b >= 0) {
    if (a > b) swap(a, b);
    a -= 1;
    b -= 2;
    if (a >= 0 && b >= 0) {
      ans++;
    }
  }
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long TT = 1;
  if (multiple_tests) cin >> TT;
  for (long long T = 1; T <= TT; T++) {
    solve();
    cout << '\n';
  }
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}
