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.
def problem1():
    a, b = list(map(int, input().split()))
    if b > a :
        b = b + a
        a = b - a
        b = b - a
    if a*b < 2 :
        print(0)
    elif a >= 2*b :
        print(b)
    else :
        print((a - b) + 2*(2*b - a) // 3)

# def problem2():
#     n, x, m = list(map(int, input().split()))
#     a = x
#     b = x
#     for _ in range(m):
#         l, r = list(map(int, input().split()))
#         if a 
#     print(s)

cases = int(input())
for _ in range(cases) :
    problem1()
    # problem2()
        