#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
using namespace std;
inline char get() {
  static char buf[30000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 30000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  register char c = get();
  register int f = 1, _ = 0;
  while (c > '9' || c < '0') f = (c == '-') ? -1 : 1, c = get();
  while (c <= '9' && c >= '0') _ = (_ << 3) + (_ << 1) + (c ^ 48), c = get();
  return _ * f;
}
int a[5000005];
signed main() {
  int t = read();
  for (register int i = 2; i <= 5000000; i++) {
    if (!a[i]) {
      for (register int j = 1; j * i <= 5000000; j++) {
        for (register int k = i * j; k % i == 0; k /= i) a[i * j]++;
      }
    }
    a[i] += a[i - 1];
  }
  while (t--) {
    int r = read(), l = read();
    printf("%d\n", a[r] - a[l]);
  }
}
