#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
template <class T>
typename T::value_type arr_sum(const T& v, int n) {
  typename T::value_type sum = 0;
  for (int i = (0); i < (n); ++i) sum += v[i];
  return sum;
}
struct Sync_stdio {
  Sync_stdio() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
  }
} _sync_stdio;
int C = 5500000;
vector<int> get_primes(int n) {
  vector<int> prime(n + 1, 1);
  prime[0] = prime[1] = 0;
  int s = sqrt(n);
  for (int i = 2; i <= s; ++i) {
    if (prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        prime[j] = 0;
      }
    }
  }
  vector<int> primes;
  for (int i = (0); i < (n + 1); ++i) {
    if (prime[i]) {
      long long t = i;
      while (t < C) {
        primes.push_back(t);
        t *= i;
      }
    }
  }
  sort(primes.begin(), primes.end());
  return primes;
}
int main() {
  vector<long long> v(C);
  vector<int> primes = get_primes(C);
  for (auto i : primes) {
    int t = i;
    while (t < C) {
      ++v[t];
      t += i;
    }
  }
  vector<long long> ps(C);
  for (int i = (1); i < (C); ++i) {
    ps[i] = ps[i - 1] + v[i];
  }
  int n;
  cin >> n;
  for (int t = (0); t < (n); ++t) {
    int a, b;
    cin >> a >> b;
    cout << ps[a] - ps[b] << "\n";
  }
}
