#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 1;
long long table[N];
bool prime[N];
void precompute() {
  memset(prime, 1, sizeof(prime));
  prime[0] = prime[1] = false;
  for (int i = 2; i < N; i++)
    if (prime[i])
      for (int j = i * 2; j < N; j += i) prime[j] = false;
  for (int i = 2; i < N; i++)
    if (prime[i]) {
      int p = 1;
      while (p * (long long)i < N) {
        p *= i;
        for (int x = p; x <= N; x += p) table[x]++;
      }
    }
  for (int i = 0; i < N; ++i) table[i + 1] += table[i];
}
int main() {
  ios::sync_with_stdio(0);
  precompute();
  int t;
  scanf("%d", &t);
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    int ans = table[a] - table[b];
    printf("%d\n", ans);
  }
}
