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.
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())

for i in range(int(input())):
    a,b = readInts()
    cnt = 0
    if a < b:
        MAX = max(min(a//2,b),min(a,b//2))
        if a - MAX*2 >= 0:
            a -= MAX*2
            b -= MAX
            cnt += MAX
        else:
            b -= MAX*2
            a -= MAX
            cnt += MAX
    #    print(a,b)
    #    print(cnt)
    else:
        MAX = min(min(a//2,b),min(a,b//2))
        if a - MAX*2 >= 0:
            a -= MAX*2
            b -= MAX
            cnt += MAX
        else:
            b -= MAX*2
            a -= MAX
            cnt += MAX
    #    print(a,b)
    #    print(cnt)
    if a < b:
        MAX = max(min(a//2,b),min(a,b//2))
        if a - MAX*2 >= 0:
            a -= MAX*2
            b -= MAX
            cnt += MAX
        else:
            b -= MAX*2
            a -= MAX
            cnt += MAX
        print(a,b)
        print(cnt)
    else:
        MAX = min(min(a//2,b),min(a,b//2))
        if a - MAX*2 >= 0:
            a -= MAX*2
            b -= MAX
            cnt += MAX
        else:
            b -= MAX*2
            a -= MAX
            cnt += MAX
        print(a,b)
        print(cnt)
