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
 
sys.setrecursionlimit(1000000) #设置最大递归深度
int1 = lambda x: int(x) - 1 #返回x-1
p2D = lambda x: print(*x, sep="\n") #输出多个元素，以换行符分割
p2S = lambda x: print(*x, sep=" ") #输出多个元素，以空格分割
def II(): return int(sys.stdin.readline()) #读一行（仅一个）整数
def MI(): return map(int, sys.stdin.readline().split()) #读一行数据，转化为int型元组
def LI(): return list(map(int, sys.stdin.readline().split())) #读一行数据，转化为int型列表
def LLI(rows_number): return [LI() for _ in range(rows_number)] 
def SI(): return sys.stdin.readline()[:-1] #读一行字符串，舍掉换行符


def main():
    _v_ = II()
    for _ in range(_v_):
        a, b = MI()
        ma = max(a, b)
        mb = min(a, b)
        if ma >= (mb << 1):
            print(mb)
        else:
            x = (2 * a - b) / 3
            y = (2 * b - a) / 3
            print(int(x + y))
        


main()