#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

// Source: Me
// Tested on: ???
// Merge by size + path compression
struct DSU {
  struct node {
    int p;  // parent
    int s;  // size
  };

  vector<node> nodes;
  DSU(int n) {
    nodes.resize(n);
    for (int i = 0; i < n; i++) {
      nodes[i].p = i;
      nodes[i].s = 1;
    }
  }

  node& operator[](int index) { return nodes[index]; }

  int size(int v) { return nodes[find(v)].s; }

  int find(int v) {
    if (nodes[v].p == v) return v;
    return nodes[v].p = find(nodes[v].p);
  }

  bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (nodes[a].s < nodes[b].s) swap(a, b);
    nodes[b].p = a;
    nodes[a].s += nodes[b].s;
    return true;
  }

  vector<vector<int>> get_components() {
    vector<vector<int>> g(nodes.size());
    for (int i =0; i < nodes.size(); i++)
      g[find(i)].push_back(i);
    g.erase(remove_if(g.begin(), g.end(), [&](vector<int>& v)->bool {
      return v.empty();
    }), g.end());
    return g;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  const int N = 1e6+7;
  vector<int> w(N, 0);
  vector<vector<int>> prime_facs(N);
  for (int i = 2; i < N; i++) {
    if (w[i] == 0) {
      for (int j = i; j < N; j += i) {
        w[j]++;
        prime_facs[j].push_back(i);
      }
    }
  }

  vector<vector<vi>> buckets(N, vector<vi>(8));
  vector<int> curr_idx(N, -1);
  vector<int> min_idx(N, -1);

  int tt;
  cin >> tt;
  while(tt--) {
    const int MAX_W = 16;
    vector<queue<int>> pq(MAX_W);
    int merges = 0;

    int l, r;
    cin >> l >> r;
    r++;
    set<int> touched;
    DSU d(r-l);
    rep(x, l, r) {
      for (int mask = 0; mask < 1<<sz(prime_facs[x]); mask++) {
        int y = 1;
        rep(i, 0, sz(prime_facs[x])) {
          if (mask>>i&1)
            y *= prime_facs[x][i];
        }
        touched.insert(y);
        //
        // this is the difference from x to the base
        int diff = sz(prime_facs[x]) - __builtin_popcount(mask);
        buckets[y][diff].push_back(x);
      }
    }

    for (auto& x : touched) {
      for (int i = 0; i < 8; i++) {
        if (sz(buckets[x][i])) {
          if (min_idx[x] == -1) {
            min_idx[x] = i;
            if (sz(buckets[x][i]) != 1) {
              curr_idx[x] = i;
              break;
            }
          } else {
            curr_idx[x] = i;
            break;
          }
        }
      }

      if (min_idx[x] == -1 || curr_idx[x] == -1) continue;
      pq[w[x] + min_idx[x] + curr_idx[x]].emplace(x);
    }

    int currw = 0;
    int64_t ans = 0;
    while(merges != r-l-1){
      while(pq[currw].empty()) currw++;
      auto x = pq[currw].front();
      pq[currw].pop();
      for (auto& v : buckets[x][curr_idx[x]]) {
        if(d.merge(v-l, buckets[x][min_idx[x]][0] - l)) {
          merges++;
          ans += currw;
        }
      }
      curr_idx[x]++;
      while(curr_idx[x] < sz(buckets[x]) && buckets[x][curr_idx[x]].empty())
        curr_idx[x]++;
      if (curr_idx[x] != sz(buckets[x])) {
        pq[w[x] + min_idx[x] + curr_idx[x]].emplace(x);
      }
    }
    cout << ans << '\n';

    for (auto& y : touched) {
      rep(i, 0, 8) {
        buckets[y][i].clear();
      }
      min_idx[y] = -1;
      curr_idx[y] = -1;
    }
  }
}