#include <bits/stdc++.h>
using namespace std;
const int MAXA = 5000005;
const int MAXT = 1000005;
int t, a[MAXT], b[MAXT], s[MAXA], MAX;
void erathos() {
  int i = 2;
  while (i <= MAX) {
    if (s[i] == 0) {
      int k = 2;
      while (i * k <= MAX) s[i * k] = i, k++;
    }
    i++;
  }
}
int main() {
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    scanf("%d%d", &a[i], &b[i]);
    MAX = max(MAX, a[i]);
  }
  erathos();
  for (int i = 2; i <= MAX; i++)
    if (s[i] == 0)
      s[i] = 1;
    else
      s[i] = s[s[i]] + s[i / s[i]];
  for (int i = 2; i <= MAX; i++) s[i] += s[i - 1];
  for (int i = 1; i <= t; i++) printf("%d\n", s[a[i]] - s[b[i]]);
}
