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())
mapi=[[]]
def recursive( d,  s):
	try:
		if mapi[d][s]!=None:
			return mapi[d][s]
	except:
		print(d,s,len(mapi),len(mapi[0]))
	ans=0;
	if (d==1 and s<2) or (s==1 and d<2) or d<=0 or s<=0:
		return 0

	ans=max(recursive(d-1,s-2)+1, recursive(d-2,s-1)+1)
	mapi[d][s]=ans
	# print(ans)
	return ans

	# if sticks>diamonds and sticks-2>=0 and diamonds-1>=0:
	# 	sticks-=2
	# 	diamonds-=1
	# 	ans+=1
	# elif diamonds>sticks and sticks-1>=0 and diamonds-2>=0:
	# 	sticks-=1
	# 	diamonds-=2
	# 	ans+=1
	# else:
	# 	if sticks-2>=0 and diamonds-1>=0:
	# 		sticks-=2
	# 		diamonds-=1
	# 		ans+=1
	# 	elif sticks-1>=0 and diamonds-2>=0:
	# 		sticks-=1
	# 		diamonds-=2
	# 		ans+=1
	# 	else:
	# 		break

for i in range(T):
	inp=input().split()
	s=int(inp[0])
	d=int(inp[1])
	ans=0
	# maxi=max(sticks,diamonds)
	# mapi=[[None]*(maxi+1)]*(maxi+1);
	# print(recursive(sticks,diamonds))
	ans=min(d,s,(d+s)//3)
	print(ans)