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.

import collections


def read():
    return input().strip()


def readInt():
    return int(input().strip())


def readList():
    return list(map(int, input().strip().split()))


def solve(a, b):
    # ans = 0

    # while a and b:
    #     [a, b] = sorted([a, b])

    #     res = b - a

    #     if res == 0:
    #         ans += (a+b)//3

    #         a -= a
    #         b -= b
    #     elif res > a:
    #         ans += a
    #         a -= a
    #         b -= 2*a
    #     else:
    #         ans += res
    #         a -= res
    #         b -= 2*res

    # return ans

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


t = readInt()
# [n,m] = readList()

for i in range(t):
    [a, b] = readList()

    print(solve(a, b))
