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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using cd = complex<double>;
#define speed                                                                  \
    ios_base::sync_with_stdio(false);                                          \
    cin.tie(0);                                                                \
    cout.tie(0);
#define ll long long
#define ull unsigned long long
#define db double
#define vi vector<ll>
#define vvi vector<vector<int> >
#define vvii vector<vector<pii> >
#define rep2(i, begin, end)                                                    \
    for (__typeof(end) i = (begin) - ((begin) > (end));                        \
         i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define endl "\n"
#define pii pair<ll, ll>
#define piii pair<ll, pair<ll, ll> >
#define mem(a, b) memset(a, b, sizeof a);
#define pb push_back
#define pf push_front
#define F first
#define S second
#define mp make_pair
#define all(v) v.begin(), v.end()
#define range(i, s) for (auto i : s)
#define sor(v) sort(v.begin(), v.end());
#define rev(v) reverse(v.begin(), v.end());
#define inf INFINITY
#define mc(a, b) memcpy(a, b, sizeof(b));
#define per(i, a, b) for (ll i = a - 1; i >= b; i--)
#define PI 3.14159265359

#define error(args...)                                                         \
    {                                                                          \
        string _s = #args;                                                     \
        replace(_s.begin(), _s.end(), ',', ' ');                               \
        stringstream _ss(_s);                                                  \
        istream_iterator<string> _it(_ss);                                     \
        err(_it, args);                                                        \
    }

void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

#define deb1(a) cout << #a << "=*" << a << endl;
#define deb2(a) cout << #a << "=@" << a << endl;
#define deb3(a) cout << #a << "=#" << a << endl;
#define deb4(a, b) cout << #a << "=" << a << " and " << #b << "=" << b << endl;
#define deb5(a, b) cout << #a << "=" << a << " and " << #b << "=" << b << endl;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
// find_by_order -> value at index
// order_of_key -> index of value

ll mod = 1000000007;
ll vis[212345] = {0};
vvi v(212345);
ll d[212345] = {0};

ll pow(ll a, ll b, ll m)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % m;
        b /= 2;
        a = (a * a) % m;
    }
    return ans;
}

int main()
{
    speed

        ll t;
    cin >> t;
    while (t--)
    {
        ll a, b;
        cin >> a >> b;
        ll m1 = min(a, b);
        ll m2 = max(a, b);
        if (m2 >= 2 * m1)
        {
            cout << m1 << endl;
            continue;
        }
        ll r = ceil((db)(2 * m1 - m2) / 3);
        if (m1 != m2)
        {
            cout << r * 2 + max(0LL, m1 - 3 * r) << endl;
            continue;
        }
        ll c = 0;
        c += (m1 / 3) * 2;
        //  m1 = m1 % 3;
        m2 = m2 - 3 * (m1 / 3);
        m1 = m1 % 3;

        if (m1 == 0)
            cout << c << endl;
        else if (m1 == 1 && m2 >= 2)
            cout << c + 1 << endl;
        else if (m1 == 1)
            cout << c << endl;
        else if (m2 >= 4)
            cout << c + 2 << endl;
        else
            cout << c + 1 << endl;
    }
}
