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 <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <numeric>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <ctime>
#include <cmath>
#include <list>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

typedef long long ll;
typedef tuple<int, int, int> tri;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef __gnu_pbds::tree<
    int,
    __gnu_pbds::null_type,
    less<int>,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update>
    ordered_set;

const ll MODULO = 1000000007;

void ftime()
{
#ifndef ONLINE_JUDGE
    cout << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
#endif
}

static int speed_increase = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

void solve()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
        swap(a, b);
    int x = b - a;
    if (x < a)
        x += 2 * ((a - x) / 3);
    else
        x = a;
    cout << x << "\n";
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    // ftime();
    return 0;
}