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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args){
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solve(in, out);
        out.close();
    }

    static String reverse(String s) {
        return (new StringBuilder(s)).reverse().toString();
    }

    static void sieveOfEratosthenes(int n, int factors[], ArrayList<Integer> ar) 
    { 
        factors[1]=1;
        int p;
        for(p = 2; p*p <=n; p++) 
        { 
            if(factors[p] == 0) 
            { 
                ar.add(p);
                factors[p]=p;
                for(int i = p*p; i <= n; i += p) 
                    if(factors[i]==0)
                        factors[i] = p; 
            } 
        } 
        for(;p<=n;p++){
            if(factors[p] == 0) 
            { 
                factors[p] = p;
                ar.add(p);
            } 
        }
    }

    static void sort(int ar[]) {
        int n = ar.length;
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++)
            a.add(ar[i]);
        Collections.sort(a);
        for (int i = 0; i < n; i++)
            ar[i] = a.get(i);
    }

    static void sort1(long ar[]) {
        int n = ar.length;
        ArrayList<Long> a = new ArrayList<>();
        for (int i = 0; i < n; i++)
            a.add(ar[i]);
        Collections.sort(a);
        for (int i = 0; i < n; i++)
            ar[i] = a.get(i);
    }

    static void sort2(char ar[]) {
        int n = ar.length;
        ArrayList<Character> a = new ArrayList<>();
        for (int i = 0; i < n; i++)
            a.add(ar[i]);
        Collections.sort(a);
        for (int i = 0; i < n; i++)
            ar[i] = a.get(i);
    }

    static long ncr(long n, long r, long mod) {
        if (r == 0)
            return 1;
        long val = ncr(n - 1, r - 1, mod);
        val = (n * val) % mod;
        val = (val * modInverse(r, mod)) % mod;
        return val;
    }

    static long max[];
    static long lz[];
    
    // static void build(long a[], int v, int tl, int tr) {
    //     if (tl == tr) {
    //         max[v] = a[tl];
            
    //     } else {
    //         int tm = (tl + tr) / 2;
    //         build(a, v*2, tl, tm);
    //         build(a, v*2+1, tm+1, tr);
    //         max[v] = max[v*2] + max[v*2+1];
    //     }
    // }

    // static void push(int v, int tl, int tr){
    //     if(tl==tr){
    //         lz[v] = 0;
    //         return;
    //     }
    //     max[2*v] += lz[v];
    //     // max[2*v] %= m;
    //     max[2*v+1] += lz[v];
    //     // max[2*v+1] %= m;
    //     lz[2*v] += lz[v];
    //     lz[2*v] %= m;
    //     lz[2*v+1] += lz[v];
    //     lz[2*v+1] %= m;
    //     lz[v] = 0;
    // }

    static void update(int v, int tl, int tr, int l, int r, long val) {
        if(tl>r||tr<l)
            return;
        if(tl>=l&&tr<=r){
            max[v] = Math.max(val, max[v]);
            return;
        }
        int tm = ((tl + tr) >> 1);
        update(v*2, tl, tm, l, r, val);
        update(v*2+1, tm+1, tr, l, r, val);
        max[v] = Math.max(max[2*v],max[2*v+1]);
    }

    static long get(int v, int tl, int tr, int l, int r) {
        if(l>tr||r<tl)
            return 0;
        if (tl >= l && tr <= r) {
            return max[v];
        }
        int tm = ((tl + tr) >> 1);
        return Math.max(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
    }

    // static int y = 0;

    static int parent[];
    static int rank[];

    static long m = 0;

    static int find_set(int v) {
        if (v == parent[v])
            return v;
        return find_set(parent[v]);
    }
    
    static void make_set(int v) {
        parent[v] = v;
        rank[v] = 1;
    }
    
    static void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (rank[a] < rank[b]){
                int tmp = a;
                a = b;
                b = tmp;
            }
            parent[b] = a;
            // if (rank[a] == rank[b])
            //     rank[a]++;
            rank[a] += rank[b];
            max1 = Math.max(max1,rank[a]);
            // System.out.println(a+" "+b+" "+rank[a]+" "+rank[b]);
        }
    }

    static int parent1[];
    static int rank1[];

    static int find_set1(int v) {
        if (v == parent1[v])
            return v;
        return find_set1(parent1[v]);
    }
    
    static void make_set1(int v) {
        parent1[v] = v;
        rank1[v] = 1;
    }
    
    static void union_sets1(int a, int b) {
        a = find_set1(a);
        b = find_set1(b);
        if (a != b) {
            if (rank1[a] < rank1[b]){
                int tmp = a;
                a = b;
                b = tmp;
            }
            parent1[b] = a;
            // if (rank1[a] == rank1[b])
            //     rank1[a]++;
            rank1[a] += rank1[b];
        }
    }

    static long max1 = 0;

    static int count = 0;
    static int count1 = 0;

    public static void solve(InputReader sc, PrintWriter pw){
        int i, j = 0;
        // int t = 1; 
        long mod = 998244353;
        // int factors[] = new int[1000001];
        // ArrayList<Integer> ar = new ArrayList<>();
        // sieveOfEratosthenes(1000000, factors, ar);
        // HashSet<Integer> set = new HashSet<>();
        // for(int x:ar){
        //     set.add(x);
        // }
        int t = sc.nextInt();
        int a[][] = new int[300000][30];
        for(i=0;i<30;i++){
            int d = (1<<i);
            for(j=1;j<300000;j++){
                a[j][i] = a[j-1][i];
                if(j%(2*d)>=d){
                    a[j][i]++;
                }
            }
        }
        u: while (t-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int min = Integer.MAX_VALUE;
            for(i=0;i<30;i++){
                min = Math.min(min,(r-l+1)-(a[r][i]-a[l-1][i]));
            }
            pw.println(min);
        }
    }

    static void KMPSearch(char pat[], char txt[], int pres[]){
        int M = pat.length;
        int N = txt.length;
        int lps[] = new int[M];
        int j = 0; 
        computeLPSArray(pat, M, lps);
        int i = 0;
        while (i < N) {
            if (pat[j] == txt[i]) {
                j++;
                i++;
            }
            if (j == M) {
                pres[i-1] = 1;
                j = lps[j - 1];
            }
            else if (i < N && pat[j] != txt[i]) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
    }
  
    static void computeLPSArray(char pat[], int M, int lps[])
    {
        int len = 0;
        int i = 1;
        lps[0] = 0; 
        while (i < M) {
            if (pat[i] == pat[len]) {
                len++;
                lps[i] = len;
                i++;
            }
            else 
            {
                if (len != 0) {
                    len = lps[len - 1];
                }
                else
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }

    static long[][] matrixMult(long a[][], long b[][], long mod){
        int n = a.length;
        int m = a[0].length;
        int p = b[0].length;
        long c[][] = new long[n][p];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<p;k++){
                    c[i][k] += a[i][j]*b[j][k];
                    c[i][k] %= mod;
                }
            }
        }
        return c;
    }

    static long[][] exp(long mat[][], long b, long mod){
        if(b==0){
            int n = mat.length;
            long res[][] = new long[n][n];
            for(int i=0;i<n;i++){
                res[i][i] = 1;
            }
            return res;
        }
        long half[][] = exp(mat, b/2, mod);
        long res[][] = matrixMult(half, half, mod);
        if(b%2==1){
            res = matrixMult(res, mat, mod);
        }
        return res;
    }

    static void countPrimeFactors(int num, int a[], HashMap<Integer,Integer> pos){
        for(int i=2;i*i<num;i++){
            if(num%i==0){
                int y = pos.get(i);
                while(num%i==0){
                    a[y]++;
                    num/=i;
                }
            }
        }
        if(num>1){
            int y = pos.get(num);
            a[y]++;
        }
    }

    static void assignAnc(ArrayList<Integer> ar[], int depth[], int sz[], int par[][] ,int curr, int parent, int d){
        depth[curr] = d;
        sz[curr] = 1;
        par[curr][0] = parent;
        for(int v:ar[curr]){
            if(parent==v)
                continue;
            assignAnc(ar, depth, sz, par, v, curr, d+1);
            sz[curr] += sz[v];
        }
    }

    static int findLCA(int a, int b, int par[][], int depth[]){
        if(depth[a]>depth[b]){
            a = a^b;
            b = a^b;
            a = a^b;
        }
        int diff = depth[b] - depth[a];
        for(int i=19;i>=0;i--){
            if((diff&(1<<i))>0){
                b = par[b][i];
            }
        }
        if(a==b)
            return a;
        for(int i=19;i>=0;i--){
            if(par[b][i]!=par[a][i]){
                b = par[b][i];
                a = par[a][i];
            }
        }
        return par[a][0];
    }

    static void formArrayForBinaryLifting(int n, int par[][]){
        for(int j=1;j<20;j++){
            for(int i=0;i<n;i++){
                if(par[i][j-1]==-1)
                    continue;
                par[i][j] = par[par[i][j-1]][j-1];
            }
        }
    }

    static long lcm(int a, int b){
        return a*b/gcd(a,b);
    }

    static class Pair1 {
        long a;
        long b;
        
        Pair1(long a, long b) {
            this.a = a;
            this.b = b;
        }
    }

    static class Pair implements Comparable<Pair> {
        int a;
        int b;
        // int c;
        
        Pair(int a, int b) {
            this.a = a;
            this.b = b;
            // this.c = c;
        }
 
        public int compareTo(Pair p) {
            if(a!=p.a)
                return p.a-a;
            return b-p.b;
        }
    }

    static class Pair2 implements Comparable<Pair2> {
        int a;
        int b;
        int c;
        
        Pair2(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
 
        public int compareTo(Pair2 p) {
            return a-p.a;
        }
    }

    static boolean isPrime(int n) { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 ||  n % 3 == 0) 
            return false; 
        for (int i = 5; i * i <= n; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 

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

    static long fast_pow(long base, long n, long M) {
        if (n == 0)
            return 1;
        if (n == 1)
            return base % M;
        long halfn = fast_pow(base, n / 2, M);
        if (n % 2 == 0)
            return (halfn * halfn) % M;
        else
            return (((halfn * halfn) % M) * base) % M;
    }

    static long modInverse(long n, long M) {
        return fast_pow(n, M - 2, M);
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 9992768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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