#include <bits/stdc++.h>
using namespace std;
long long f[5000001], spf[5000001];
bool pr[5000001];
void prm() {
  for (int i = 2; i < 5000001; ++i) spf[i] = i & 1 ? i : 2;
  for (long long i = 3; i * i < 5000001; i += 2) {
    if (spf[i] == i) {
      for (long long j = i * 2; j < 5000001; j += i) {
        if (spf[j] == j) spf[j] = i;
      }
    }
  }
}
void factorize() {
  f[1] = 1;
  for (int i = 2; i <= 5000000; ++i) {
    if (spf[i] == i) {
      f[i] += f[i - 1] + 1;
      continue;
    }
    int n = i;
    while (n > 1) {
      if (f[n]) {
        f[i] += (f[n] - f[n - 1]);
        break;
      }
      n /= spf[n];
      ++f[i];
    }
    f[i] += f[i - 1];
  }
}
int main() {
  prm();
  factorize();
  int n, a, b;
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &a, &b);
    long long an = f[a] - f[b];
    printf("%lld\n", an);
  }
}
