#include <bits/stdc++.h>
using namespace std;
template <class T>
T _max(T a, T b) {
  return a > b ? a : b;
}
template <class T>
T _min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T _gcd(T a, T b) {
  if (!b) return a;
  return _gcd(b, a % b);
}
template <class T>
T _lcm(T a, T b) {
  return (a * b) / _gcd(a, b);
}
template <class T>
T _abs(T a) {
  return (a < 0) ? -a : a;
}
template <class T>
T _pow(T a, T b) {
  T ret = 1;
  for (T i = 1; i <= b; i++) {
    ret *= a;
  }
  return ret;
}
bool Check(long long int N, long long int pos) {
  return (bool)(N & (1 << pos));
}
long long int Set(long long int N, long long int pos) {
  return N = N | (1 << pos);
}
long long int N = 5000005;
long long int status[200000];
long long int prime[2000000];
long long int dp[5000001];
long long int y;
void sieve() {
  long long int i, j, sqrtN;
  sqrtN = sqrt(N);
  for (i = 3; i <= sqrtN; i += 2) {
    if (Check(status[i >> 5], i & 31) == 0) {
      for (j = i * i; j <= N; j += (i << 1)) {
        status[j >> 5] = Set(status[j >> 5], j & 31);
      }
    }
  }
  prime[y++] = 2;
  for (i = 3; i <= N; i += 2)
    if (Check(status[i >> 5], i & 31) == 0) prime[y++] = i;
}
void factors_calculation() {
  memset(dp, 0, sizeof(dp));
  long long int p, i, j;
  for (i = 2; i <= 5000000; i++) {
    p = i;
    bool flag = false;
    for (j = 0; prime[j] <= sqrt(i) && j <= y; j++) {
      if (p % prime[j] == 0) {
        flag = true;
        p /= prime[j];
        dp[i] += (dp[p] + 1);
        break;
      }
    }
    if (!flag) {
      dp[i] += 1;
    }
  }
  for (i = 1; i <= 5000000; i++) {
    dp[i] += dp[i - 1];
  }
}
int main() {
  sieve();
  factors_calculation();
  long long int test, a, b, i;
  scanf("%lld", &test);
  for (i = 1; i <= test; i++) {
    scanf("%lld", &a);
    scanf("%lld", &b);
    cout << dp[a] - dp[b] << "\n";
  }
  return 0;
}
