#include <bits/stdc++.h>
using namespace std;
const long long MAX_b = 5e6;
bool isPrime[MAX_b + 1];
int Prime[MAX_b];
int dp[MAX_b + 1];
int sum[MAX_b + 2];
void ini() {
  memset(isPrime + 2, true, sizeof(bool) * (MAX_b - 1));
  for (long long i = 2; i <= MAX_b; ++i)
    if (isPrime[i])
      for (long long j = i; i * j <= MAX_b; ++j) isPrime[i * j] = false;
  int sz = 0;
  for (int i = 0; i <= MAX_b; ++i)
    if (isPrime[i]) Prime[sz++] = i;
  for (long long i = 1; i <= MAX_b; ++i)
    for (long long j = 0; j < sz && i * Prime[j] <= MAX_b; ++j)
      dp[i * Prime[j]] = max(dp[i * Prime[j]], dp[i] + 1);
  for (int i = 0; i <= MAX_b; ++i) sum[i + 1] = sum[i] + dp[i];
}
int main() {
  ini();
  int t;
  scanf("%d", &t);
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    int ans = sum[a + 1] - sum[b + 1];
    printf("%d\n", ans);
  }
}
