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.
tll=int(input())
while(tll>0):
	tll-=1
	a,b=map(int, input().split())
	ans=0
	while(a+b>=3):
		if (a==0 or b==0):
			break
		if (a==1 or b==1):
			ans+=1
			break
		if (a==2 and b==2):
			ans+=1
			break
		if (a>b):
			temp=b
			b=max(b-(a-b), 0)
			a=b
			ans+=temp-b
		elif(b>a):
			temp=a
			a=max(0, a-(b-a))
			b=a
			ans+=temp-a
		else:
			sub=(a//3)*2
			ans+=sub
			a=a%3
			b=b%3

	print(ans)






	

	




		











