#include <bits/stdc++.h>
using namespace std;
int t, a, b;
int cnt[5 * int(1e6 + 100)], ans[5 * int(1e6 + 100)];
bool ok[5 * int(1e6 + 100)];
void solve() {
  for (int i = 2; i < 5 * int(1e6 + 100); i++) {
    if (!ok[i]) {
      for (int j = 1; i * j < 5 * int(1e6 + 100); j++) {
        int cur = i * j;
        while (cur % i == 0) cur /= i, cnt[i * j]++;
        ok[i * j] = true;
      }
    }
  }
  for (int i = 1; i < 5 * int(1e6 + 100); i++) ans[i] = cnt[i] + ans[i - 1];
}
int main() {
  if (0 & 1) freopen("input", "r", stdin);
  if (0 & 2) freopen("output", "w", stdout);
  solve();
  scanf("%d", &t);
  for (int i = 0; i < t; i++) {
    scanf("%d%d", &a, &b);
    printf("%d\n", ans[a] - ans[b]);
  }
  return 0;
}
