#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int lp[N], rep[N], cnt[N];
vector<int> par;
vector<int> divisors[N];
pair<int, int> fir[N];
pair<int, int> sec[N];
tuple<int, int, int> mine[N];

int find(int u) {
  if (par[u] < 0) return u;
  return par[u] = find(par[u]);
}

bool join(int u, int v) {
  u = find(u); v = find(v);
  if (u != v) {
    par[v] = u; return true;
  }
  return false;
}



void solve() {
  int l, r; cin >> l >> r;
  vector<int> v;
  for (int i = l; i <= r; i++)
    v.push_back(rep[i]);
  int n = v.size();
  par.assign(n, -1);
  int cmp = n, res = 0;
  while (cmp > 1) {
    for (int i = 1; i <= r; i++)
      fir[i] = sec[i] = {1e9, -1};
    for (int i = 0; i < n; i++)
      mine[i] = {1e9, 0, 0};
    for (int i = 0; i < n; i++)
      for (int x : divisors[v[i]]) {
        if (cnt[v[i]] < fir[x].first) {
          if (fir[x].second != find(i))
            sec[x] = fir[x];
          fir[x] = {cnt[v[i]], find(i)};
        } else if (cnt[v[i]] < sec[x].first && find(i) != sec[x].second)
          sec[x] = {cnt[v[i]], find(i)};
      }
    
    for (int i = 0; i < n; i++)
      for (int x : divisors[v[i]]) {
        auto thr = make_pair(cnt[v[i]], find(i));
        if (sec[x].second < 0) continue;
        if (thr.second != fir[x].second)
          mine[find(i)] = min(mine[find(i)],
          {thr.first + fir[x].first - cnt[x],
          thr.second, fir[x].second});
        if (thr.second != sec[x].second)
          mine[find(i)] = min(mine[find(i)],
          {thr.first + sec[x].first - cnt[x],
          thr.second, sec[x].second});
      }
    
    for (int i = 0; i < n; i++) {
      auto [w, u, v] = mine[i];
      if (join(u, v)) {
        res += w; cmp--;
      }
    }
  }
  cout << res << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  iota(lp, lp + N, 0);
  for (int i = 2; i * i < N; i++)
    if (lp[i] == i)
      for (int j = i * i; j < N; j += i)
        if (lp[j] == j) lp[j] = i;
  for (int i = 1; i < N; i++) {
    int x = i;
    rep[i] = 1;
    bool square = false;
    vector<int> factors;
    while (x > 1) {
      int y = lp[x];
      x /= y;
      rep[i] *= y;
      cnt[i]++;
      factors.push_back(y);
      while (x % y == 0) {
        square = true; x /= y;
      }
    }
    if (square) continue;
    int n = factors.size();
    for (int mask = 0; mask < (1 << n); mask++) {
      x = 1;
      for (int j = 0; j < n; j++)
        if (mask >> j & 1) x *= factors[j];
      divisors[i].push_back(x);
    }
  }
    
  int t; cin >> t;
  while (t--) solve();
}