#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000000 + 100;
int cnt;
int prime[maxn], phi[maxn];
long long num[maxn];
int tmp[maxn];
long long sum[maxn];
bool visit[maxn];
void Prime(int n) {
  cnt = 0;
  memset(visit, 0, sizeof(visit));
  for (int i = (2), _i = (n - 1); i <= _i; ++i) {
    if (!visit[i]) prime[cnt++] = i, phi[i] = i - 1;
    for (int j = 0; j < cnt && (long long)i * prime[j] < (long long)n; ++j) {
      long long k = (long long)i * prime[j];
      visit[k] = true;
      if (i % prime[j] == 0) {
        phi[k] = phi[i] * prime[j];
        break;
      } else
        phi[k] = phi[i] * (prime[j] - 1);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  Prime(maxn);
  for (int i = (1), _i = (maxn); i <= _i; ++i) tmp[i] = i;
  for (int i = (0), _i = (cnt - 1); i <= _i; ++i) {
    for (int j = prime[i]; j < maxn; j += prime[i]) {
      while (tmp[j] % prime[i] == 0) {
        ++num[j];
        tmp[j] /= prime[i];
      }
    }
  }
  for (int j = (2), _j = (maxn - 1); j <= _j; ++j) {
    if (tmp[j] != 1) ++num[j];
    sum[j] = sum[j - 1] + num[j];
  }
  int t, a, b;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &a, &b);
    printf("%I64d\n", sum[a] - sum[b]);
  }
  return 0;
}
