#include <bits/stdc++.h>
using namespace std;
bool p[5000020];
int prime[5000020];
void criba() {
  p[0] = false;
  p[1] = false;
  for (int i = 2; i <= 5000000; i++) p[i] = true;
  for (int i = 2; i <= 5000000; i++) {
    if (p[i]) {
      prime[i] = 1;
      for (int h = 2; i * h <= 5000000; h++) {
        p[i * h] = false;
        if (h >= i and h % i == 0) {
          int cnt = 0, x = i * h;
          while (x % i == 0) {
            cnt++;
            x = x / i;
          }
          prime[i * h] += cnt;
        } else
          prime[i * h]++;
      }
    }
  }
  int sum = 0;
  for (int i = 1; i <= 5000000; i++) prime[i] += prime[i - 1];
}
int main() {
  int tc, a, b;
  cin >> tc;
  memset(prime, 0, sizeof(prime));
  criba();
  while (tc--) {
    scanf("%d%d", &a, &b);
    printf("%d\n", prime[a] - prime[b]);
  }
  return 0;
}
