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.
#
#    ------------------------------------------------
#         Fast Tests Competitive Python Template
#    ------------------------------------------------
#    Author: prophet "神"
#    Version: 1V3uJkowFG
#    License: GNU Affero General Public License v3.0
#    Location: 218.92.0.135
#    ------------------------------------------------
#

testing_mode = True

import sys, traceback

test_data = ""
final_output = ""

def input(input_format = 0, multi = 0):

    if multi > 0: return [input(input_format) for x in range(multi)]
    else:
        next_line = next(test_data, None).strip() if test_data else sys.stdin.readline()

        if input_format == 0: formatted_input = [next_line]
        elif input_format == 1: formatted_input = list(map(int, next_line.split()))
        elif input_format == 2: formatted_input = list(map(float, next_line.split()))
        elif input_format == 3: formatted_input = next_line.split()
        elif input_format == 4: formatted_input = (lambda x: [x[0], list(map(int, x[1:]))])(next_line.split())
        elif input_format == 5: formatted_input = (lambda x: [x[0], list(map(float, x[1:]))])(next_line.split())
        else: formatted_input = [next_line]

        return formatted_input

def log(*args):
    if testing_mode: print(*args)

def out(output_line, output_format = 0, newline = True):

        global final_output

        formatted_output = ""

        if output_format == 0: formatted_output = str(output_line)
        elif output_format == 1: formatted_output = " ".join(map(str, output_line))
        elif output_format == 1: formatted_output = "\n".join(map(str, output_line))

        if testing_mode: final_output += formatted_output + "\n" * newline
        else: print(formatted_output, end = "\n" if newline else "")

test_inputs = [
# Input 1
"""
4
4 4
1000000000 0
7 15
8 7

""",
# Input 2
"""
$$$
""",
# Input 3
"""
$$$
""",
# Input 4
"""
$$$
"""
]

test_outputs = [
# Output 1
"""
2
0
7
5

""",
# Output 2
"""
$$$
""",
# Output 3
"""
$$$
""",
# Output 4
"""
$$$
"""
]

#
#   >>>>>>>>>>>>>>> START OF SOLUTION <<<<<<<<<<<<<<
#

def solve():

    for z in range(input(1)[0]):

        a, b = input(1)

        x = max(a, b)
        y = min(a, b)

        if x > 2 * y:
            x = 2 * y

        k = (x + y) // 3

        out(k)

    return

#
#   >>>>>>>>>>>>>>>> END OF SOLUTION <<<<<<<<<<<<<<<
#

def run_all(overwrite_testing = False):

    global testing_mode, final_output, test_data

    testing_mode = overwrite_testing and testing_mode

    if testing_mode:

        tests_failed = 0

        for test_number, (test_in, test_out) in enumerate(zip(test_inputs, test_outputs)):

            final_output = ""

            if test_in.lstrip()[:3] == "$$$": continue

            test_data = iter([i for i in test_in.split("\n") if i])

            print(f"Test Case #{test_number + 1}:")
            print("<" * 20)

            fail = False
            verdict = "\033[92m\033[1mPASS\033[0m"

            try:
                solve()
                final = final_output.rstrip("\n")
                raw_out = iter(map(str, final.split("\n"))) if final else iter(())
            except Exception:
                raw_out = ""
                fail = True
                print("\033[95m")
                traceback.print_exc()
                print("\033[0m")

            if raw_out:
                if test_out.lstrip()[:3] == "$$$":
                    verdict = "\033[94m\033[1mSKIP\033[0m"
                    print("\033[94m" + '\n'.join(list(raw_out)) + "\033[0m")
                else:
                    for line_out in [i for i in test_out.split("\n") if i]:
                        line_raw = next(raw_out, "% None %")
                        if line_raw == line_out.strip():
                            print(f"\033[92m{line_raw}\033[0m")
                        else:
                            print(f"\033[91m{line_raw}\033[0m")
                            fail = True

                    line_raw = next(raw_out, None)
                    while line_raw:
                        print(f"\033[91m{line_raw}\033[0m")
                        line_raw = next(raw_out, None)
                        fail = True

            print(">" * 20)

            if fail:
                verdict = "\033[91m\033[1mFAIL\033[0m"
                tests_failed += 1

            print(verdict + "\n")

        if tests_failed: print(f"\033[91m\033[1m{tests_failed} TEST{'S' if tests_failed > 1 else ''} FAILED!\033[0m")
        else: print(f"\033[92m\033[1mALL TESTS PASSED!\033[0m")

    else:

        test_data = False
        solve()

run_all(False)

