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 sys
import math

input = sys.stdin.readline

#
# for _ in range(int(input())):
#     n, m = map(int, input().split())
#     matrix = []
#     for line in range(n):
#         matrix.append([int(x) for x in input().split()])
#
#     ans = 0
#     nod = math.gcd((m - 1), (n - 1))
#     if nod != 1:
#         c = m - 1
#         for i in range(0, n, (n - 1) // nod):
#             matrix[i][c] = 2
#             c -= (m - 1) // nod
#     else:
#         matrix[0][m-1] = 2
#         matrix[n-1][0] = 2
#     print(matrix)
#
#     for i in range(n):
#        for j in range(m):
#             v = matrix[i][j]
#             if v == 2:
#                 continue
#
#             h = matrix[n - i - 1][m - j - 1]
#             if v != h:
#                 ans += 1
#                 matrix[n - i - 1][m - j - 1] = v
#
#
#     print(ans)


# for _ in range(int(input())):
#     n, x, m = map(int, input().split())
#
#     ans = 0
#     for _ in range(m):
#         pass
#
#

for _ in range(int(input())):
    a, b = map(int, input().split())

    ans = 0
    while a and b:
        a, b = min(a, b), max(a, b)
        v = min(b - a, a, b)

        ans += v
        a -= v
        b -= v * 2

        if a == b:
            ans += (a // 3) * 2
            a %= 3
            if a == 2:
                ans += 1
            break

    print(ans)
