#include <bits/stdc++.h>
using namespace std;
long long dev[5000005];
long long S[5000005];
long long pri[5000005];
void sieve() {
  memset(dev, -1, sizeof dev);
  int p = 0;
  for (int i = 2; i <= 5000005; i++) {
    if (dev[i] != -1) continue;
    pri[p++] = i;
    for (long long j = 1; j < 5000005; j++) {
      if (i * j >= 5000005) break;
      dev[i * j] = i;
    }
  }
}
int main() {
  sieve();
  for (int i = 1; i < 5000005; i++) {
    int x = i;
    while (x > 1) {
      int d = dev[x];
      S[i]++;
      x /= d;
    }
  }
  for (int i = 2; i <= 5000005; i++) {
    S[i] += S[i - 1];
  }
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%I64d\n", S[a] - S[b]);
  }
  return 0;
}
