#include <bits/stdc++.h>
using namespace std;
const int mx = 5000000;
int p[mx + 4];
void precalc() {
  for (int i = 2; i <= mx; ++i)
    if (!p[i]) {
      ++p[i];
      for (int j = i + i; j <= mx; j += i) {
        int jj = j;
        while (jj % i == 0) {
          ++p[j];
          jj /= i;
        }
      }
    }
  for (int i = 1; i <= mx; ++i) p[i] += p[i - 1];
}
int main() {
  precalc();
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", p[a] - p[b]);
  }
}
