/* #pragma GCC optimize("Ofast") */
/* #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") */
/* #pragma GCC optimize("unroll-loops") */
#include "bits/extc++.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: ecnerwala
// Templates for Policy Based Data Structures
struct splitmix64_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

using namespace __gnu_pbds;
template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = gp_hash_table<K, V, Hash>;

template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, null_type, Hash>;

template <class T, class Compare = less<>>
using ordered_set =
    tree<T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;

// 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<vector<int>> prime_facs(N);
  for (int i = 2; i < N; i++) {
    if (prime_facs[i].empty()) {
      for (int j = i; j < N; j += i) {
        prime_facs[j].push_back(i);
      }
    }
  }

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

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


    int l, r;
    cin >> l >> r;
    r++;
    set<int> touched;
    DSU d(r-l);
    int64_t ans = 0;
    vi matter;
    for (int i = l; i < r; i++){
      if (d.size(i) == 1) {
        matter.push_back(i);
      }
      for (int j = 2*i; j < r; j+= i) {
        if (d.merge(i-l, j-l)) {
          ans += sz(prime_facs[j]);
        }
      }
    }
    for (auto& x : matter) {
      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);
        buckets[y].resize(8);
        // 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[sz(prime_facs[x]) + min_idx[x] + curr_idx[x]].emplace(x);
    }

    int currw = 0;
    while(merges != sz(matter) - 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[sz(prime_facs[x]) + min_idx[x] + curr_idx[x]].emplace(x);
      }
    }
    cout << ans << '\n';

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