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

    def doble(x, y):
        if x >= 2 * y:
            return y
        else:

            return x

    def iguales(z, w):
        if z == w:
            if z == 0 or w == 0:
                return 0
            if z == 1 and w == 1:
                return 0
            if z > 1:
                coins = (z//3) * 2
                if z % 3 == 0 or z % 3 == 1:
                    return coins
                if z % 3 == 2:
                    return (coins + 1)



    if a == b:
        print(iguales(a, b))


    else:

        if a >= 2 * b or b >= 2 * a:
            print(doble(a, b))

        else:
            if a < b:

                dif = b-a
                a = a - dif
                b = a
                parte = iguales(a, b)
                monedas = parte + dif
                print(monedas)


                '''cont = 0
                while True:
                    a = a - 1
                    b = b - 2
                    cont = cont + 1
                    if a == b:
                        parte = iguales(a, b)
                        print(cont + parte)
                        cont = 0
                        parte = 0
                        break'''
            if b < a:

                dif = a - b
                b = b - dif
                a = b
                parte = iguales(a, b)
                monedas = parte + dif
                print(monedas)


                '''conta = 0
                while True:
                    b = b - 1
                    a = a - 2
                    conta = conta + 1
                    if a == b:
                        parte = iguales(a, b)
                        print(conta + parte)
                        conta = 0
                        parte = 0
                        break'''