#include <bits/stdc++.h>
using namespace std;
const int MAX = 5000000;
int p[MAX / 2 + 1];
int q[MAX + 1];
void calc() {
  for (int s = 0; s <= MAX / 2; s++) {
    if (p[s]) continue;
    int t = (s + 1) * 2 + 1;
    for (int u = s; u <= MAX / 2; u += t) p[u] = t;
  }
  for (int i = 2; i <= MAX; i++) {
    int n = i, m = 0;
    while (n > 1) {
      m++;
      n /= n & 1 ? p[n / 2 - 1] : 2;
    }
    q[i] = q[i - 1] + m;
  }
}
int main(int argc, char **argv) {
  calc();
  stringstream sin, sout;
  char buf[65536];
  while (cin) {
    cin.read(buf, sizeof(buf));
    sin.write(buf, cin.gcount());
  }
  int t;
  sin >> t;
  for (int n = 0; n < t; n++) {
    int a, b;
    sin >> a >> b;
    sout << q[a] - q[b] << '\n';
  }
  cout << sout.str();
  return 0;
}
