You are given an array consisting of all integers from [l, r] inclusive. For example, if l = 2 and r = 5, the array would be [2, 3, 4, 5]. What's the minimum number of elements you can delete to make the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of the array non-zero?

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t cases follow.

The first line of each test case contains two integers l and r (1 ≤ l ≤ r ≤ 2 ⋅ 10^5) — the description of the array.

Output

For each test case, output a single integer — the answer to the problem.

Example

Input


5
1 2
2 8
4 5
1 5
100000 200000


Output


1
3
0
2
31072

Note

In the first test case, the array is [1, 2]. Currently, the bitwise AND is 0, as 1\ \& \ 2 = 0. However, after deleting 1 (or 2), the array becomes [2] (or [1]), and the bitwise AND becomes 2 (or 1). This can be proven to be the optimal, so the answer is 1.

In the second test case, the array is [2, 3, 4, 5, 6, 7, 8]. Currently, the bitwise AND is 0. However, after deleting 4, 5, and 8, the array becomes [2, 3, 6, 7], and the bitwise AND becomes 2. This can be proven to be the optimal, so the answer is 3. Note that there may be other ways to delete 3 elements.
//package com.company;

import java.math.BigInteger;
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {

    //public static FastScanner fs = new FastScanner();
    public static Scanner sc = new Scanner(System.in);
    public static PrintWriter out = new PrintWriter(System.out);
    public static int inf = 1000000007;
    public static BigInteger infb = new BigInteger("1000000007");
    public static long lmax= (long) 1e18;
    public static boolean flag=false;
    public static StringBuilder sb=new StringBuilder();

//     public static class WeightedGraph {
//         static class Edge {
//             int source;
//             int destination;
//             int weight;
//
//             public Edge(int source, int destination, int weight) {
//                 this.source = source;
//                 this.destination = destination;
//                 this.weight = weight;
//             }
//         }
//
//         static class Graph {
//             int vertices;
//             LinkedList<Edge>[] adjacencylist;
//
//             Graph(int vertices) {
//                 this.vertices = vertices;
//                 adjacencylist = new LinkedList[vertices];
//
//                 for (int i = 0; i < vertices; i++) {
//                     adjacencylist[i] = new LinkedList<>();
//                 }
//             }
//
//             void addEdge(char source, char destination, int weight) {
//                 Edge edge = new Edge(source, destination, weight);
//                 adjacencylist[source].addFirst(edge);
//             }
//
//         }
//
//     }
//
//    static int minimumCostSimplePath(int u, int destination,
//                                     boolean[] visited,
//                                     WeightedGraph.Graph graph)
//    {
//
//
//        if (u == destination)
//            return 0;
//
//        visited[u] = true;
//
//        int ans = inf;
//
//        // Traverse through all
//        // the adjacent nodes
//        for(int i = 0; i < graph[0].length; i++)
//        {
//            if (graph[u][i] != inf && !visited[i])
//            {
//
//                // Cost of the further path
//                int curr = minimumCostSimplePath(i,
//                        destination, visited, graph);
//
//                // Check if we have reached the
//                // destination
//                if (curr < inf)
//                {
//
//                    // Taking the minimum cost path
//                    ans = Math.min(ans, graph[u][i] + curr);
//                }
//            }
//        }
//
//        visited[u] = false;
//
//        return ans;
//    }


    /////// For printing elements in 1D-array

    public static void print1d(long[] arr) {
        for (long x : arr) {
            out.print(x + " ");
        }
        out.println();
    }

    /////// For printing elements in 2D-array

    public static void print2d(long[][] arr) {
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++){
                out.print(arr[i][j]+" ");
            }
            out.println();
        }
        out.println();
    }

    /////// For freq of elements in array

    public static long[] freq(long[] freq_arr, long[] arr) {
        for (long j : arr) {
            freq_arr[(int) j]++;
        }

        return freq_arr;
    }

    /////// For sum elements in array

    public static int sum(int[] arr) {

        int sum = 0;

        for (int j : arr) {
            sum += j;
        }
        return sum;
    }

    /////// For storing elements in array 1D

    public static long[] scan1d(long[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextLong();
        }

        return arr;
    }

    /////// For storing elements in array 2D

    public static long[][] scan2d(long[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i][0] = sc.nextLong();
            arr[i][1] = sc.nextLong();
        }

        return arr;
    }

    /////// For copying elements in array

    public static long[] copy_arr(long[] arr, long[] arr1) {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = arr[i];
        }

        return arr;
    }

    /////// For GCD

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    /// gcd of array

    static long findGCD(long arr[], long n)
    {
        long result = 0;
        for (long element: arr){
            result = gcd(result, element);

            if(result == 1)
            {
                return 1;
            }
        }

        return result;
    }

    //////// Forprime

    public static boolean isPrime(long n) {
        if (n < 2)
            return false;
        if (n == 2 || n == 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        long sqrtN = (long) Math.sqrt(n) + 1;
        for (long i = 6L; i <= sqrtN; i += 6) {
            if (n % (i - 1) == 0 || n % (i + 1) == 0)
                return false;
        }
        return true;
    }

    //////Using array as Set
    public static boolean[] arr_set(boolean[] arr, int n) {
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            arr[x] = true;
        }

        return arr;
    }

    /// Fidning min in array
    public static long min_arr(long[] arr){
        long min=arr[0];

        for(int i=0;i<arr.length;i++){
            min=Math.min(min,arr[i]);
        }

        return min;
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }


    public static long fact(long n) {

        long fact = 1;
        for (long i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }

    public static long nCr(long n, long r) {
        long res = 1;
        for (long i = 0; i < r; i++) {
            res *= (n - i);
            res /= (i + 1);
        }
        return res;

    }

    public static long pCr(long n, long r)
    {
        return fact(n) / (fact(n-r));
    }

    static boolean isSubSequence(String str1, String strm,
                                 int m, int n)
    {
        int j = 0;

        for (int i = 0; i < n && j < m; i++)
            if (str1.charAt(j) == strm.charAt(i))
                j++;

        return (j == m);
    }

    public class bp{
        int x;
        int y;
        int val;

        bp(int x,int y,int val){
            this.x=x;
            this.y=y;
            this.val=val;
        }
    }

    public class Tree{
        class Node{
            int val;
            Node lc;
            Node rc;
        }


    }

    ///creating pair class

    public static class Pair{
        int x;
        int y;

    }

    public static boolean cmp(int a, int b)
    {
        return a > b;
    }

    static boolean isPowerOfTwo(long n)
    {
        if(n==0)
            return false;

        return (long)(Math.ceil((Math.log(n) / Math.log(2)))) ==
                (long)(Math.floor(((Math.log(n) / Math.log(2)))));
    }

    //// Max sum subarray


//  Arrays.sort(freq, (a, b) -> a[0] - b[0]);
//  (fact(n)/(fact(i)*fact(n-i)))

    public static long pt(long n)
    {
        long cnt = -1;
        while (n != 0)
        {
            n /= 2;
            cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {

        //File in = new File("input.txt");
        //Writer wr= new FileWriter("output.txt");
        //Scanner ssc=new Scanner(in);
        //BigInteger n = new BigInteger(String.valueOf(sc.nextInt()));
        //StringBuilder sb= new StringBuilder();

        int t=sc.nextInt();

        long Dp[][] = new long[200002][21];

        for(long i=1;i<=200001;i++){
            long  check = i, idx = 0;
            while (check>0){
                Dp[(int) i][(int) idx++] += (check % 2);
                check /= 2;
            }
            for(long j=0;j<=20;j++){
                Dp[(int) i][(int) j] += Dp[(int) (i - 1)][(int) j];
            }
        }

        while(t-->0){
            long l=sc.nextLong();
            long r=sc.nextLong();

            //vll check(20, 0);
            long maxElement = 0;

            for(long i=0;i<=20;i++){
                maxElement = Math.max(maxElement, Dp[(int) r][(int) i] - Dp[(int) (l - 1)][(int) i]);
            }

            out.println(r-l+1-maxElement);

        }


        out.flush();

    }
}