#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;

const int N = 1e6 + 7;
const int Inf = 1e9;

int par[N];

int get(int a) { return (a == par[a] ? a : par[a] = get(par[a])); }

bool join(int a, int b) {
  a = get(a);
  b = get(b);
  if (a != b) {
    par[a] = b;
    return true;
  } else {
    return false;
  }
}

int mn[N][2];
int cmp[N][2];
int cur_cmp[N];
int best_c[N];
int best_edge[N];
int cost[N];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  vector<bool> is_prime(N, true);
  vector<bool> is_good(N, true);
  for (int d = 2; d < N; ++d) {
    if (is_prime[d]) {
      ll d_sq = (ll)d * d;
      for (int x = d; x < N; x += d) {
        cost[x] += 1;
        if (x != d) {
          is_prime[x] = false;
          if (x % d_sq == 0) {
            is_good[x] = false;
          }
        }
      }
    }
  }
  vector<vector<int>> subms(N);
  for (int d = 1; d < N; ++d) {
    if (is_good[d]) {
      for (int x = d; x < N; x += d) {
        subms[x].push_back(d);
      }
    }
  }
  int t;
  cin >> t;
  while (t--) {
    int l, r;
    cin >> l >> r;
    ll ans = 0;
    for (int i = l; i <= r; ++i) {
      par[i] = i;
    }
    int cmps = r - l + 1;
    while (cmps > 1) {
      for (int i = l; i <= r; ++i) {
        cur_cmp[i] = get(i);
        best_c[i] = Inf;
        best_edge[i] = -1;
      }
      for (int d = 1; d <= r; ++d) {
        if (is_good[d]) {
          mn[d][0] = mn[d][1] = Inf;
          cmp[d][0] = cmp[d][1] = -1;
          for (int x = d; x <= r; x += d) {
            if (x < l)
              continue;
            int x_cmp = cur_cmp[x];
            int x_cost = cost[x] - cost[d];
            for (int k = 0; k < 2; ++k) {
              if (x_cost < mn[d][k] && (k == 0 || x_cmp != cmp[d][0])) {
                swap(x_cost, mn[d][k]);
                swap(x_cmp, cmp[d][k]);
              }
            }
          }
        }
      }
      for (int x = l; x <= r; ++x) {
        int best_cost = Inf;
        int best_cmp = -1;
        for (int d : subms[x]) {
          for (int k = 0; k < 2; ++k) {
            if (mn[d][k] < best_cost && cmp[d][k] != cur_cmp[x]) {
              best_cost = mn[d][k];
              best_cmp = cmp[d][k];
            }
          }
        }
        assert(best_cmp != -1);
        best_cost += cost[x];
        if (best_cost < best_c[cur_cmp[x]]) {
          best_c[cur_cmp[x]] = best_cost;
          best_edge[cur_cmp[x]] = best_cmp;
        }
      }
      for (int i = l; i <= r; ++i) {
        if (best_edge[i] != -1) {
          if (join(i, best_edge[i])) {
            --cmps;
            ans += best_c[i];
          }
        }
      }
    }
    cout << ans << '\n';
  }
}

/*
5
1 1
4 5
1 4
1 9
19 810

2
27 30
183704 252609
*/