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.
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long a, b, c, d, e, i, j, k, l, r, a1, a2, a3, b1, b2, b3, x1, y1, x, y,
      t, f, l1, r1;
  string s, s1, s2, s3, T;
  vector<long long> v, v1, v2, o;
  cin >> t;
  for (f = 0; f < t; f++) {
    long long o = 0;
    cin >> l >> r;
    v = {};
    for (i = 0; i < 20; i++) {
      v.push_back(r - l + 1);
    }
    j = 1;
    long long maxx = 0;
    l1 = l;
    r1 = r;
    int maxp = 0;
    for (i = 0; i < 20; i++) {
      l = l1;
      r = r1;
      long long o = 0;
      int maxp;
      if (((l / j) % 2) != 1) {
        l = (((l - 1) / j) + 1) * j;
      } else {
        o += min(((((l - 1) / j) + 1) * j) - l, r - l + 1);
        l = ((((l - 1) / j) + 1) * j);
      }
      if (l < (r + 1)) {
        if ((r / j) % 2 == 0) {
          r = ((r) / j) * j;
        } else {
          o += min(r - (((r) / j) * j), r - l);
          r = ((r) / j) * j;
        }
        if (l < (r + 1)) {
          if (((l / j) % 2) == 1) {
            if (l == r) {
              o++;
            } else {
              o += ((((r - l + 1) / (j)) + 1) / 2) * j;
            }
          } else {
            if (l != r) {
              o += ((((r - l + 1) / (j))) / 2) * j;
            }
          }
        }
      }
      j = j * 2;
      if (o > maxx) {
        maxx = o;
        maxp = j;
      }
    }
    cout << (r1 - l1 + 1) - maxx << "\n";
  }
}
