#include <bits/stdc++.h>
using namespace std;
const long long maxn = 5e6 + 10;
long long dp[maxn];
bool mark[maxn] = {0};
void kom() {
  mark[1] = 1;
  for (long long i = 2; i < maxn; i++) {
    dp[i] += dp[i - 1];
    if (!mark[i]) {
      dp[i]++;
      for (long long j = 2 * i; j < maxn; j += i) {
        mark[j] = 1;
        long long komm = j;
        while (komm % i == 0) {
          dp[j]++;
          komm /= i;
        }
      }
    }
  }
}
int a, b;
void get_input() { cin >> a >> b; }
void solve() { cout << dp[a] - dp[b] << '\n'; }
void output() {}
int main() {
  ios_base ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  kom();
  cin >> tc;
  while (tc--) {
    get_input(), solve(), output();
  }
  return 0;
}
