#include <bits/stdc++.h>
using namespace std;
long long int spf[5000001], cum_sum[5000001] = {0};
vector<long long int> factors;
void store() {
  for (long long int i = 1; i <= 5000000; i++) i % 2 ? spf[i] = i : spf[i] = 2;
  for (long long int i = 3; i * i <= 5000000; i += 2) {
    if (spf[i] == i) {
      for (long long int j = (i * i); j <= 5000000; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
void prime_factorization(long long int n) {
  while (n != 1) {
    factors.push_back(spf[n]);
    n /= spf[n];
  }
}
int main() {
  long long int q, a, b, sum = 0;
  store();
  cum_sum[1] = 1;
  for (long long int i = 2; i <= 5000000; i++) {
    prime_factorization(i);
    cum_sum[i] = cum_sum[i - 1] + factors.size();
    factors.clear();
  }
  scanf("%lld", &q);
  while (q--) {
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", cum_sum[a] - cum_sum[b]);
  }
  return 0;
}
