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
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush,heappop,heapify
from itertools import permutations,combinations
from itertools import accumulate as ac
mod = int(1e9)+7
mod = 998244353
 
 
ip = lambda : int(stdin.readline())
inp = lambda: map(int,stdin.readline().split())
ips = lambda: stdin.readline().rstrip()
out = lambda x : stdout.write(str(x)+"\n")

t = ip()
for _ in range(t):
    a,b = inp()
    if a>b:
        a,b =b,a
    x,y = a,b
    ans = 0
    ch = y//2
    if x>= ch:
        ans += ch
        y -= 2*ch
        x -= ch
    else:
        ans += x
        y -= 2*x
        x = 0
    if x>y:
        x,y = y,x
    ch = y//2
    if x>= ch:
        ans += ch
        y -= 2*ch
        x -= ch
    else:
        ans += x
        y -= 2*x
        x = 0
    ans1 = 0
    y,x = a,b
    ch = y//2
    if x>= ch:
        ans1 += ch
        y -= 2*ch
        x -= ch
    else:
        ans1 += x
        y -= 2*x
        x = 0
    if x>y:
        x,y = y,x
    ch = y//2
    if x>= ch:
        ans1 += ch
        y -= 2*ch
        x -= ch
    else:
        ans1 += x
        y -= 2*x
        x = 0
    x,y = a,b
    ans3 = 0
    if x>= 3 and y>=3:
        m = min(x//3,y//3)
        ans3 += 2*m
        x %= 3
        y %= 3
    if x>y:
        x,y = y,x
    if x == 1 and y == 2:
        ans3 += 1
    ans = max(ans,ans3)
    out(ans)
    
    
    
    
                
                
            
                    
            
        
        
    
        
            
                    
            
