#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> pf(1e7+1);
  for (int p = 2; p < pf.size(); p++) if (pf[p] == 0) {
    for (int x = p; x < pf.size(); x += p) pf[x]++;
  }
  vector<int> cum(pf.size());
  for (int i = 1; i < pf.size(); i++) cum[i] = cum[i-1] + (pf[i]%2 ? -1 : 1);

  int N, A, B;
  while (cin >> N) {
    for (int i = 0; i < N; i++) {
      cin >> A >> B;
      cout << cum[B] - cum[A-1] << endl;
    }
  }
}