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 sys import stdin, stdout  
import collections
import heapq
import itertools
import functools
import math
import operator
import string

ALPHABET = string.ascii_lowercase
DIGITS = string.digits

def read_line():
    return stdin.readline().strip()
def read_int():
    return int(read_line())
def read_arr():
    return read_line().split(' ')
def read_int_arr():
    return [int(x) for x in read_arr()]
def query_interactive(s):
    print(s)
    stdout.flush()

def solve():
    a, b = read_int_arr()
    if a > b:
        a, b = b, a
    num_singular = min(b - a, a, b // 2)
    a -= num_singular
    b -= 2 * num_singular
    if a > b:
        a, b = b, a
    num_both = min(a, b) // 3
    a -= num_both * 3
    b -= num_both * 3
    rem = 0
    if b >= 2 and a >= 1:
        rem = 1
    print(num_singular + num_both * 2 + rem)


def main():
    T = 1
    T = read_int()
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()