#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const string nl = "\n";
vector<long long> hld, hld1((long long)5e6 + 10);
vector<bool> prime((long long)5e6 + 10, true);
void solve() {
  long long a, b;
  cin >> a >> b;
  cout << hld1[a] - hld1[b] << nl;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  prime[0] = prime[1] = 0;
  for (long long i = 1; i * i <= ((long long)(prime).size()); ++i) {
    if (prime[i]) {
      for (long long j = i * i; j <= ((long long)(prime).size()); j += i) {
        prime[j] = 0;
      }
    }
  }
  for (long long i = 0; i < ((long long)(prime).size()); ++i) {
    if (prime[i]) {
      hld.push_back(i);
    }
  }
  for (long long i = 0; i < ((long long)(hld).size()); ++i) {
    for (long long j = hld[i]; j <= ((long long)(hld1).size()); j += hld[i]) {
      long long hld2 = j;
      while (hld2 % hld[i] == 0) {
        hld2 /= hld[i];
        hld1[j]++;
      }
    }
  }
  for (long long i = 1; i < ((long long)(hld1).size()); ++i) {
    hld1[i] += hld1[i - 1];
  }
  long long T;
  cin >> T;
  while (T--) {
    solve();
  }
}
