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;
#define int long long int
#define cin(n) scanf("%lld",&n)
#define cins(st) scanf("%s",st)
void cinarray(int *n,int len){while(len--)scanf("%lld",n++);}
void coutarray(int *n,int len){while(len--)printf("%lld ",*(n++));}
int i, j, k, x, y, z, test;

main()
{
    cin(test);
    while(test--){
        int a, b;
        cin(a);cin(b);
        if(a>b)swap(a,b);
        if(a*2<=b)i=b;
        else {i=b-a;a-=i;if(a%3)i+=a/2;else i+=a/2+1;}
        cout<<i<<endl;
    }
}

