#include <bits/stdc++.h>
using namespace std;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long double pii = 3.14159265359;
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 5000001;
int lp[MX + 1];
vector<int> pr;
void sieve() {
  for (int i = 2; i <= MX; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= MX;
         ++j)
      lp[i * pr[j]] = pr[j];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  sieve();
  vector<long long> dp(MX);
  dp[1] = 1;
  for (int x = 2; x < (MX); x++) {
    dp[x] = dp[x - 1];
    int cpy = x;
    while (cpy != 1) {
      dp[x]++;
      cpy /= lp[cpy];
    }
  }
  int Test_case;
  cin >> Test_case;
  while (Test_case-- != 0) {
    int A, B;
    cin >> A >> B;
    cout << dp[A] - dp[B] << nl;
  }
  return 0;
}
