#include <bits/stdc++.h>
using namespace std;
int prime[5000005];
int cnt[5000005];
void get_primes(long long MAX) {
  for (long long x = 2; x <= MAX; x++)
    if (!prime[x]) {
      cnt[x] = 1;
      for (long long j = x * 2; j <= MAX; j += x) prime[j] = x;
    }
}
int main() {
  int t;
  cin >> t;
  get_primes(5000001);
  for (int i = 2; i < 5000001; i++) {
    if (cnt[i] == 1) continue;
    cnt[i] = cnt[i / prime[i]] + 1;
  }
  for (int i = 2; i < 5000003; i++) cnt[i] += cnt[i - 1];
  int a, b;
  while (t--) {
    scanf("%d %d", &a, &b);
    printf("%d\n", cnt[a] - cnt[b]);
  }
  return 0;
}
