#include <bits/stdc++.h>
using namespace std;
long long int t, i, p[5000005], ans[5000005], j, k, a, b;
int main() {
  cin >> t;
  for (i = 2; i < 5000005; i++) {
    p[i] = 1;
  }
  for (i = 2; i < 5000005; i++) {
    if (p[i] == 1) {
      k = i;
      while (k < 5000005) {
        j = 1;
        while (k * j < 5000005) {
          p[k * j] = 0;
          ans[k * j]++;
          j++;
        }
        k *= i;
      }
    }
  }
  for (i = 3; i < 5000005; i++) {
    ans[i] = ans[i - 1] + ans[i];
  }
  while (t) {
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", ans[a] - ans[b]);
    t--;
  }
  return 0;
}
