#include <bits/stdc++.h>
using namespace std;
inline long long msb(long long val) { return 63 - __builtin_clzll(val); }
inline int msb(int val) { return 31 - __builtin_clz(val); }
template <class T>
bool chmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
const int mod = 1e9 + 7, N = 5e6 + 3;
int n, m, k;
int pr[N];
void solve(int test_case) {
  int i, j;
  int l, r;
  cin >> l >> r;
  cout << pr[l] - pr[r] << '\n';
  return;
}
signed main() {
  for (int i = 2; i < N; i++)
    if (pr[i] == 0)
      for (int j = i; j < N; j += i) {
        int x = j;
        while (x % i == 0) x /= i, pr[j]++;
      }
  for (int i = 2; i < N; i++) pr[i] += pr[i - 1];
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int _T;
  cin >> _T;
  for (int T_CASE = 1; T_CASE <= _T; T_CASE++) solve(T_CASE);
  return 0;
}
