#include <bits/stdc++.h>
using namespace std;
const long long int MAXN = 5e6 + 10000;
int small[MAXN], prime[MAXN], dp[MAXN];
void sieve() {
  for (int i = 2; i <= MAXN; i++) {
    if (prime[i] == 1) {
      continue;
    }
    small[i] = i;
    for (int j = 2 * i; j <= MAXN; j += i) {
      prime[j] = 1;
      small[j] = i;
    }
  }
}
int main() {
  sieve();
  for (int i = 2; i <= MAXN; i++) {
    int x = i, ct = 0;
    while (x != 1) {
      x /= small[x];
      ct++;
    }
    dp[i] = dp[i - 1] + ct;
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", dp[a] - dp[b]);
  }
}
