#include <bits/stdc++.h>
using namespace std;
long long int binomialCoeff(long long int n, long long int k) {
  long long int res = 1;
  if (k > n - k) k = n - k;
  for (int i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long int power(long long int x, long long int y) {
  long long int temp;
  if (y == 0) return 1;
  temp = power(x, y / 2);
  if (y % 2 == 0)
    return temp * temp;
  else
    return x * temp * temp;
}
const int n = 5000001;
vector<int> primes;
void Sieve(int n) {
  vector<bool> prime(n + 1, true);
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  for (int p = 2; p <= n; p++)
    if (prime[p]) primes.push_back(p);
}
const int Nmax = 200005;
long long int dp[n];
void precal() {
  dp[1] = 0;
  for (int j = 0; j < primes.size(); j++) {
    long long int x = primes[j];
    long long int t = x;
    int c = 0;
    for (int i = x; i < n; i += x) {
      int num = i;
      while (num % x == 0) {
        dp[i]++;
        num /= x;
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    dp[i] += dp[i - 1];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  Sieve(n);
  precal();
  while (t--) {
    long long int a, b;
    cin >> a >> b;
    cout << dp[a] - dp[b] << "\n";
  }
}
