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
sys.setrecursionlimit(10000)
# default is 1000 in python


t = int(input())
# t = 1

for _ in range(t):
	# n = int(input())

	a, b = input().split()
	a = int(a)
	b = int(b)

	# n, m = input().split() 
	# n = int(n)
	# m = int(m)
	if a > 2*b:
		print(b)
	elif b > 2*a:
		print(a)
	else:
		x = (2*a - b )/3
		y = (2*b - a )/3
		# if (2*b - a ) % 3 != 0:
		# 	x += 1
		print(int(x+y))

# try:

	# raise Exception
# except:
	# print("-1")
	

# thenos.sort(key=lambda x: x[2], reverse=True)

# int(math.log(max(numbers)+1,2))

# 2**3 (power)

# a,t = (list(x) for x in zip(*sorted(zip(a, t))))

# to copy lists use .copy()

# pow(p, si, 1000000007) for modular exponentiation

# map(int, input().split())


# my_dict.pop('key', None)
# This will return my_dict[key] if key exists in the dictionary, and None otherwise.



