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.
def get_input():
 t = int(input())
 arr = []
 for i in range(t):
  a,b = list(map(int, input().split(' ')))
  arr.append([a,b])
 return arr


def equalize(small, big):
 sub = big-small
 steps = min(sub-1, small) 
 return small-steps, big-steps*2, steps


def f1(ab):
 a,b = ab
 if a==0 or b==0: print(0); return 
 
 part0 = 0
 if abs(a-b)>1:
  if a<b:
   a, b, part0 = equalize(a,b)
  else:
   b, a, part0 = equalize(b,a)
 if a==0 or b==0: print(part0); return

 part1 = min(a//3, b//3)*2
 a_rest = a-min(a//3, b//3)*3
 b_rest = b-min(a//3, b//3)*3
 part2 = min(max(a_rest, b_rest)//2, min(a_rest,b_rest)//1)

 print(part0+part1+part2)


arr = get_input()
list(map(f1,arr))