#include <bits/stdc++.h>
const int N = 5000000;
int c[N + 4], d[N + 4];
int main() {
  for (int i = 2; i <= N; ++i)
    if (!c[i])
      for (int j = i; j <= N; j += i) c[j] = i;
  for (int i = 2; i <= N; ++i) c[i] = 1 + c[i / c[i]], d[i] = c[i] + d[i - 1];
  int n, a, b;
  scanf("%d", &n);
  while (n-- > 0 && 2 == scanf("%d%d", &a, &b)) printf("%d\n", d[a] - d[b]);
}
