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.*;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

public class B {

    private final boolean MULTI_TEST = true;
    private final String FILE_NAME = "";

    private void solve() {
        int l = ri(), r = ri();
        int[] countBits = new int[30];
        int nCount = 0;
        int n = 1;
        while(n < l) n*=2;
        int delta = Integer.MIN_VALUE;
        while(n/2 <= r) {
            delta = Math.max(delta, Math.min(r + 1, n) - Math.max(l, n/2));
            n*=2;
        }


        int lx = l - l%2, rx = r + r%2;
        nCount = (rx - lx)/2;
        int res = Math.max(0, r - l + 1 - Math.max(delta, nCount));
        out.println(res);
    }

    //////////////////////////////////////////////////////////////////

    long sqrtLong(long x) {
        long root = (long) Math.sqrt(x);
        while (root * root > x) --root;
        while ((root + 1) * (root + 1) <= x) ++root;
        return root;
    }

    int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

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

    int phi(int n) {
        int result = n;
        for (int i = 2; i * i <= n; ++i)
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        if (n > 1)
            result -= result / n;
        return result;
    }

    int factmod(int n, int p) {
        int res = 1;
        while (n > 1) {
            res = (res * ((n / p) % 2 == 1 ? p - 1 : 1)) % p;
            for (int i = 2; i <= n % p; ++i)
                res = (res * i) % p;
            n /= p;
        }
        return res % p;
    }

    int binpow(int a, int n) {
        int res = 1;
        while (n != 0) {
            if ((n & 1) != 0)
                res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    String solPyatnashki() {
        int a[] = new int[16];
        for (int i = 0; i < 16; ++i)
            a[i] = ri();

        int inv = 0;
        for (int i = 0; i < 16; ++i)
            if (a[i] != 0)
                for (int j = 0; j < i; ++j)
                    if (a[j] > a[i])
                        ++inv;
        for (int i = 0; i < 16; ++i)
            if (a[i] == 0)
                inv += 1 + i / 4;


        return ((inv & 1) != 0 ? "No Solution" : "Solution Exists");
    }

    boolean isPrime(int number) {
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return number > 1;
    }

    boolean[] primes(int border) {
        boolean[] isPrimes = new boolean[border + 1];
        Arrays.fill(isPrimes, true);
        isPrimes[0] = false;
        isPrimes[1] = false;
        for (int i = 2; i < border + 1; i++) {
            if (!isPrimes[i]) continue;
            for (int k = i * 2; k < border; k += i) {
                isPrimes[k] = false;
            }
        }
        return isPrimes;
    }

    void sort(int[] arr) {
        Integer[] a = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            a[i] = arr[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
    }

    void sort(long[] arr) {
        Long[] a = new Long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            a[i] = arr[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
    }

    int max(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    long max(long[] a) {
        long max = Long.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    int min(int[] a) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) min = a[i];
        }
        return min;
    }

    long min(long[] a) {
        long min = Long.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) min = a[i];
        }
        return min;
    }

    long sum(int[] a) {
        long s = 0;
        for(int i = 0; i < a.length; i++) {
            s+=a[i];
        }
        return s;
    }

    long fastMod(String s1, long n2) {
        long num = 0;
        for (int i = 0; i < s1.length() - 1; i++) {
            num += Integer.parseInt(String.valueOf(s1.charAt(i)));
            num *= 10;
            if (num >= n2) {
                num = num % n2;
            }
        }
        return (num + Integer.parseInt(String.valueOf(s1.charAt(s1.length() - 1)))) % n2;
    }

    //////////////////////////////////////////////////////////////////

    private boolean yesNo(boolean yes) {
        return yesNo(yes, "YES", "NO");
    }

    private boolean yesNo(boolean yes, String yesString, String noString) {
        out.println(yes ? yesString : noString);
        return yes;
    }

    //////////////////////////////////////////////////////////////////

    private long rl() {
        return Long.parseLong(rs());
    }

    private double rd() {
        return Double.parseDouble(rs());
    }

    private int[] ria(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = ri();
        return a;
    }

    private int ri() {
        return Integer.parseInt(rs());
    }

    private String rs() {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) return null;
            tok = new StringTokenizer(nextLine);
        }

        return tok.nextToken();
    }

    private String readLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    //////////////////////////////////////////////////////////////////

    private BufferedReader in;
    private StringTokenizer tok;
    private PrintWriter out;

    private void initFileIO(String inputFileName, String outputFileName) throws FileNotFoundException {
        in = new BufferedReader(new FileReader(inputFileName));
        out = new PrintWriter(outputFileName);
    }

    private void initConsoleIO() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
    }

    private void initIO() throws IOException {
        Locale.setDefault(Locale.US);

        if (!FILE_NAME.isEmpty()) {
            initFileIO(FILE_NAME + ".in", FILE_NAME + ".out");
        } else {
            if (new File("input.txt").exists()) {
                initFileIO("input.txt", "output.txt");
            } else {
                initConsoleIO();
            }
        }

        tok = new StringTokenizer("");
    }

    //////////////////////////////////////////////////////////////////

    private void run() {
        try {
            long timeStart = System.currentTimeMillis();
            initIO();
            if (MULTI_TEST) {
                int t = ri();
                while (t-- > 0) {
                    solve();
                    out.flush();
                }
            } else
                solve();
            out.close();
            long timeEnd = System.currentTimeMillis();
            System.err.println("Time(ms) = " + (timeEnd - timeStart));
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException(e);
        }
    }

    public static void main(String[] args) {
        new B().run();
    }

    ///////////////////////////////////////////////////////////////////
}
