#include <bits/stdc++.h>
long long mpow(long long a, long long n, long long mod) {
  long long ret = 1;
  long long b = a;
  while (n) {
    if (n & 1) ret = (ret * b) % mod;
    b = (b * b) % mod;
    n >>= 1;
  }
  return (long long)ret;
}
using namespace std;
using namespace std;
long long sum[(int)5e6 + 4];
bool chk[(int)5e6 + 4];
vector<int> prim;
void compute() {
  for (int i = 2; i <= sqrt((int)5e6 + 4); i++) {
    if (chk[i]) continue;
    prim.push_back(i);
    for (int j = 2 * i; j < (int)5e6 + 4; j += i) {
      chk[j] = 1;
    }
  }
  for (int i = 2; i <= (int)5e6 + 4 - 4; i++) {
    if (!chk[i]) {
      sum[i] = 1;
      continue;
    }
    int k = i;
    for (int j = 0; j < prim.size(); j++) {
      if (!chk[k]) {
        sum[i]++;
        k = 1;
        break;
      }
      while (k % prim[j] == 0) {
        k /= prim[j];
        sum[i]++;
        if (sum[k] != 0) {
          sum[i] += sum[k];
          k = 1;
          break;
        }
      }
      if (k == 1) break;
    }
  }
  for (int i = 2; i <= (int)5e6 + 4 - 4; i++) {
    sum[i] += sum[i - 1];
  }
}
void solve() {
  int x, y;
  scanf("%d%d", &x, &y);
  printf("%lld\n", sum[x] - sum[y]);
}
int main() {
  compute();
  int t = 1;
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}
