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 maxEmeralds(long long a, long long b) {
  long long res = 0, stickRemains = a, dimondRemains = b, temp;
  if ((stickRemains >= 2 * dimondRemains) ||
      (dimondRemains >= 2 * stickRemains)) {
    if (stickRemains > dimondRemains) {
      return dimondRemains;
    } else {
      return stickRemains;
    }
  }
  if (stickRemains >= dimondRemains && stickRemains % 2 == 1) {
    temp = stickRemains / 2;
    stickRemains %= 2;
    dimondRemains -= temp;
    res += temp;
  } else if (dimondRemains >= stickRemains && dimondRemains % 2 == 1) {
    temp = dimondRemains / 2;
    dimondRemains %= 2;
    stickRemains -= temp;
    res += temp;
  } else {
    if (stickRemains <= dimondRemains) {
      temp = stickRemains / 3;
      res += temp * 2;
      stickRemains %= 3;
      dimondRemains -= temp * 3;
      if (stickRemains == 2 && dimondRemains >= 4) {
        res += 2;
      }
    } else {
      temp = dimondRemains / 3;
      res += temp * 2;
      dimondRemains %= 3;
      stickRemains -= temp * 3;
      if (dimondRemains == 2 && stickRemains >= 4) {
        res += 2;
      }
    }
  }
  if ((stickRemains >= 1 && dimondRemains >= 2) ||
      (stickRemains >= 2 && dimondRemains >= 1)) {
    res++;
  }
  return res;
}
int main() {
  long long t, a, b;
  cin >> t;
  for (long long i = 0; i < t; i++) {
    cin >> a >> b;
    cout << maxEmeralds(a, b) << endl;
  }
  return 0;
}
