#include <bits/stdc++.h>
using namespace std;
long long dp[5000000 + 1];
int f[5000000 + 1], lp[5000000 + 1], t, a, b;
int main() {
  vector<int> pr;
  for (int i = 2; i <= 5000000; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j = 0;
         j < (int)pr.size() && pr[j] <= lp[i] && i * 1ll * pr[j] <= 5000000;
         ++j)
      lp[i * pr[j]] = pr[j];
  }
  dp[1] = 1;
  for (int i = 2; i <= 5000000; ++i) {
    f[i] = f[i / lp[i]] + 1;
    dp[i] = dp[i - 1] + f[i];
  }
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &a, &b);
    printf("%d\n", dp[a] - dp[b]);
  }
}
