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;
long long fact(long long n) { return (n == 1 || n == 0) ? 1 : n * fact(n - 1); }
long long absol(long long n) {
  if (n < 0) n = -n;
  return n;
}
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= 1000000007;
  for (; b; b >>= 1) {
    if (b & 1) res = (res * a) % 1000000007;
    a = (a * a) % 1000000007;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long binaryToDecimal(long long n) {
  long long num = n;
  long long dec_value = 0;
  long long base = 1;
  long long temp = num;
  while (temp) {
    long long last_digit = temp % 10;
    temp = temp / 10;
    dec_value += last_digit * base;
    base = base * 2;
  }
  return dec_value;
}
string binary = bitset<8>(5).to_string();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  for (long long i = 0; i < t; ++i) {
    long long a, b;
    cin >> a >> b;
    long long ans = 0, h, s;
    if (a > b) {
      h = a;
      s = b;
    } else {
      h = b;
      s = a;
    }
    if (2 * s <= h)
      ans = s;
    else {
      ans += (h - s);
      h -= 2 * ans;
      s -= ans;
      ans += (h / 3) * 2;
      h %= 3;
      s %= 3;
      if (h + s > 2) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}
