#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e6 + 2;
const int SQRT = 5e3;
const double PI = acos(-1);
const int INF = 2e9;
int p[MAXN], d[MAXN], cnt[MAXN], t, i, a, b;
long long j;
inline int readChar();
template <class T = int>
inline T readInt();
inline int readChar() {
  int c = getchar();
  while (c <= 32) c = getchar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-') s = -1, c = getchar();
  while ('0' <= c && c <= '9')
    x = (x << 1) + (x << 3) + (c - '0'), c = getchar();
  return s == 1 ? x : -x;
}
int main() {
  for (i = 2; i < 5e3; i++)
    if (!d[i]) {
      d[i] = 0;
      for (j = i * i; j < MAXN; j += i) d[j] = i;
    }
  for (i = 2; i < MAXN; i++)
    if (!d[i])
      cnt[i] = 1;
    else
      cnt[i] = cnt[i / d[i]] + 1;
  for (i = 1; i < MAXN; i++) p[i] = p[i - 1] + cnt[i];
  t = readInt();
  for (i = 0; i < t; i++) {
    a = readInt();
    b = readInt();
    printf("%d\n", p[a] - p[b]);
  }
  return 0;
}
