#include <bits/stdc++.h>
using namespace std;
vector<long long> moves(5000001), dp(5000001);
const int N = 5000000;
vector<bool> prime(N + 1, true);
void precompute() {
  for (int i = 2; i <= N; i++) {
    if (prime[i])
      for (int j = i; j <= N; j += i) {
        int count = 0, n = j;
        while (n % i == 0) count++, n /= i;
        moves[j] += count, prime[j] = false;
      }
  }
  for (int i = 1; i <= N; i++) dp[i] += dp[i - 1] + moves[i];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  precompute();
  long long t;
  cin >> t;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    cout << dp[a] - dp[b] << "\n";
  }
  return 0;
}
