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.
__author__ = 'Devesh Bajpai'

'''
https://codeforces.com/problemset/problem/1366/A

Solution: No matter we take 2 sticks and 1 diamond, or 1 stick and 2 diamonds, we collectively use 3 items
from the pool of sticks and diamonds to make 1 end product. Hence the answer seems to be (a + b)/3. But there
can be constraints to the number of sticks and diamonds available. 
Imagine a scenario of 998 sticks and 1 diamond. We could say (998 + 1)/3 = 333 end products are possible. But
As soon as we use use the 1 diamond for first product, we don't have any more diamonds left to use. Hence the
remaining 998 end products cannot be made. Therefore, the final answer need to take the constraint min(a,b) 
also in consideration. 
'''


def solve(a, b):

    return min(min(a, b), (a + b)/3)


if __name__ == "__main__":

    t = int(raw_input())

    results = list()
    for _ in xrange(0, t):
        a, b = map(int, raw_input().split(" "))
        results.append(solve(a, b))

    for result in results:
        print result
