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 region Competitive Definitions
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using u32 = uint32_t;
using u64 = uint64_t;

#define all(a) begin(a), end(a)
#define endl '\n'
#define rep(n) for (int i=0; i<(n); ++i)
#define ff(a, x) for (auto& a: x)
#define TT int tt; cin >> tt; while (tt--)

// Math
template<typename T>
inline auto sq(T x) { return x * x; }

// Inputs
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

template<typename T>
void re(T &x);

template<typename T>
void re(vector<T> &v);

template<typename T, typename... Q>
void re(T &x, Q &... y);

template<typename T>
void re(T &x) { cin >> x; }

template<typename T>
void re(vector<T> &v) { ff(x, v) re(x); }

template<typename T, typename... Q>
void re(T &x, Q &... y) {
    re(x);
    re(y...);
}

#pragma endregion

int main() {
    IOS;
    TT {
        ll a, b;
        re(a, b);
        ll ans{};
        while (a > 0 && b > 0 && a + b >= 3) {
//            printf("%lld %lld\n", a, b);
            ll c;
            if (a >= b) {
                c = min(b, a / 2);
                if (c > 1)--c;
                ans += c;
                a -= 2 * c;
                b -= c;
            } else {
                c = min(a, b / 2);
                if (c > 1)--c;
                ans += c;
                a -= c;
                b -= 2 * c;
            }
        }
        cout << ans << endl;
    };
    return 0;
}