#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template <class T> bool chmin(T &a, T b) {
  if (a <= b)
    return 0;
  a = b;
  return 1;
}
template <class T> bool chmax(T &a, T b) {
  if (a >= b)
    return 0;
  a = b;
  return 1;
}

struct UnionFind {
  vector<ll> uf;
  UnionFind(ll n) : uf(n, -1) {}
  ll root(ll x) {
    if (uf[x] < 0)
      return x;
    return uf[x] = root(uf[x]);
  }
  bool unite(ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x == y)
      return 0;
    if (uf[x] > uf[y])
      swap(x, y);
    uf[x] += uf[y];
    uf[y] = x;
    return 1;
  }
};

void solve() {
  int l, r;
  cin >> l >> r;
  struct edge {
    int to, c;
  };
  const int n = r + 1;
  vector<vector<edge>> g(n + n);
  const auto add_edge = [&](int u, int v, int c) {
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  };
  vector<int> w(n);
  rep(p, 2, n) {
    if (w[p] != 0)
      continue;
    for (int i = p; i < n; i += p) {
      w[i]++;
    }
    for (int i = 1; i * p < n; i++)
      add_edge(i, i * p, i % p ? 1 : 0);
  }
  rep(i, l, r + 1) add_edge(i, n + i, w[i]);

  struct outer_edge {
    int u, v, c;
  };
  vector<outer_edge> edges;

  struct node {
    int v, f;
    int c;
    bool operator<(const node &r) const { return c > r.c; }
  };
  priority_queue<node> pq;
  const int inf = 1e8;
  vector<int> dist(n + n, inf);
  vector<int> from(n + n, -1);
  rep(i, l, r + 1) pq.push({n + int(i), int(i), 0});
  while (!pq.empty()) {
    const auto [v, f, d] = pq.top();
    pq.pop();
    if (dist[v] != inf && from[v] != f) {
      edges.push_back({from[v], f, dist[v] + d});
      continue;
    }
    dist[v] = d;
    from[v] = f;
    for (const auto &[to, c] : g[v]) {
      if (dist[to] == inf)
        pq.push({to, f, d + c});
    }
  }

  int ans = 0;
  UnionFind uf(n);
  sort(all(edges), [](const auto &e, const auto &f) { return e.c < f.c; });
  int cnt = 0;
  for (const auto &[u, v, c] : edges) {
    if (uf.unite(u, v))
      cnt++, ans += c;
  }

  assert(cnt == r - l);

  cout << ans / 2 << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}