#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 1;
long long t, a, b, k, dp[N];
int main() {
  ;
  for (int i = (2); i < (N); i += 1) {
    if (!dp[i])
      for (int j = i; j < N; j += i) dp[j] = dp[j / i] + 1;
  };
  for (int i = (0); i < (N); i += 1) dp[i] += dp[i - 1];
  cin >> t;
  while (t--) {
    scanf("%d%d", &a, &b);
    printf("%d\n", dp[a] - dp[b]);
  }
}
