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 java.awt.Point;
    import java.io.InputStreamReader;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.lang.reflect.Array;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Optional;
    import java.util.Queue;
    import java.util.Set;
    import java.util.TreeMap;
    import java.util.TreeSet;

    public class Codeforces {



        public static void main(String[] args) throws java.lang.Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           int t = Integer.parseInt(br.readLine());
           while(t-- >0){
            String[] s = br.readLine().trim().split(" ");
            int a1 = Integer.parseInt(s[0]);
            int b1 = Integer.parseInt(s[1]);
            
            int a2 = a1;
            int b2 = b1;
            
            int ans1 = Math.min((a1 / 2), b1);
            int ans2 = Math.min(a1, b1/2);
            if(Math.abs(a1 - b1) == 1){
                System.out.println(Math.max(ans1, ans2) + 1);
            }
            else System.out.println(Math.max(ans1, ans2));
            
        }
            
            
        }
        }

         

