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

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]

testCases = int(input())
answers = []
for _ in range(testCases):
	#take input
	a, b = input_split()
	a, b = max(a,b), min(a,b)

	if a/2 <= b:
		# pass
		x = (2*a - b)//3
		y = (2*b - a)//3

		if (2*(x+1) + y <= a and (x+1)+ 2*y <=b ):
			ans = x + y +1
		elif(2*(x) + y+1 <= a and (x+1)+ 2*(y+1) <=b ):
			ans = x+y +1
		else:
			ans = x + y
	else:
		# pass		
		ans = b
	# pure_y = 
	# to_check = ()

	# ans = 0
	# ans += (b//3)*2

	# rem = b%3
	# used = (b//3)*3
	# if rem == 0:
	# 	pass
	# elif rem == 1:
	# 	ans += (1 if a - used >= 2 else 0)
	# else:
	# 	#rem is 2
	# 	if a - used >= 4:
	# 		ans += 2
	# 	else:
	# 		ans += 1
	# ans = min(a//2, b)

	answers.append(ans)

print(*answers, sep = '\n')
