#include <bits/stdc++.h>
using namespace std;
long long const n = 5000005;
long long fact[n];
long long dp[n];
void fun() {
  for (int i = 2; i < n - 1; i++) {
    if (fact[i] == i) {
      for (long long j = 2 * 1ll * i; j < n - 1; j += i) {
        if (fact[j] == j) fact[j] = i;
      }
    }
  }
}
long long calc(int x) {
  int temp = fact[x];
  int ans = 0;
  while (x > 1) {
    temp = fact[x];
    while (temp == fact[x]) {
      ans++;
      x = x / fact[x];
    }
  }
  return ans * 1ll;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  for (int i = 1; i < n - 1; i++) {
    fact[i] = i * 1ll;
  }
  fun();
  dp[1] = 0;
  for (int i = 2; i < n - 1; i++) {
    dp[i] = calc(i) + dp[i - 1];
  }
  int t, a, b;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &a);
    scanf("%d", &b);
    printf("%I64d\n", -dp[b] + dp[a]);
  }
  return 0;
}
