#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxN = 1e6 + 5;
const int BRD = 5e6 + 2;
int n, k, l, r, type, a, d, m, t, b;
bool prime[BRD + 5];
int sum[BRD + 5], divisor[BRD + 5];
void sieve() {
  for (int i = 2; i <= BRD; i++) {
    prime[i] = true;
    divisor[i] = i;
  }
  for (int i = 2; i * i <= BRD; i++) {
    if (prime[i]) {
      for (int j = i * i; j <= BRD; j += i) {
        prime[j] = false;
        divisor[j] = i;
      }
    }
  }
  for (int i = 2; i <= BRD; i++) {
    int ans = 0;
    int x = i;
    while (x != 1) {
      x /= divisor[x];
      ans++;
    }
    sum[i] = sum[i - 1] + ans;
  }
}
int main() {
  scanf("%d", &t);
  sieve();
  while (t--) {
    scanf("%d%d", &a, &b);
    printf("%d\n", sum[a] - sum[b]);
  }
  return 0;
}
