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 main():
    t = int(input())
    for i in range(t):
        a, b = map(int, input().split())

        ukupno = 0
        maxi = 0
        a1, b1 = a, b #  showel
        if a1 >= b1*2:
            maxi = b1
        else:
            if a1 // 2 <= b:
                maxi = a1 // 2

            if a1 % 2 != 0:
                a1 = 1
                b1 -= a // 2

                if b1 >= a1 * 2:
                    # if a1 > maxi:
                    maxi += a1
                else:
                    if b1 // 2 <= a1:
                       # if b // 2 > maxi:
                        maxi += b // 2

        a2, b2 = a, b
        if b2 >= a2*2:
            if a2 > maxi:
                maxi = a2
        else:
            if b2 // 2 <= a2:
                if b2 // 2 > maxi:
                    maxi = b2 // 2

                if b2 % 2 != 0:
                    b2 = 1
                    a2 -= b2//2
                    if a2 >= b2 * 2:
                        maxi += b2
                    else:
                        if a2 // 2 <= b:
                            maxi += a2 // 2

        print(maxi)


if __name__ == '__main__':
    main()
