// Sample solution for "Exploding CPU" problem
// Stein Norheim 2003
//
// Read about Zeisel numbers at http://mathworld.wolfram.com/ZeiselNumber.html
//
// Method:
//  Make a sorted list of all Zeisel numbers by looping over
//  all relevant values of A and B.

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

typedef vector<int> intvector;

class Primes {
public:
  intvector primes;
  intvector factor;
  Primes(int limit);
  void setPrime(int newPrime);
  bool isPrime(int num);
  int smallestFactor(int num);
  void setFactor(int num, int prime);
  void getZeisels(intvector& dest, int A, int B);
};

void Primes::setPrime(int newPrime) {
  primes.push_back(newPrime);
  factor[newPrime]=newPrime;
}

void Primes::setFactor(int num, int prime) {
  factor[num] = prime;
}

Primes::Primes(int limit) {
  factor.reserve(limit);
  factor.resize(limit);
  setPrime(2);

  int tempprime;
  for (int i=3; i<limit; i++) {
    int j=0;
    tempprime=1;
    while (tempprime*tempprime<i) {
      tempprime=primes[j++];
      if (i % tempprime==0) break;
    }
    if (i % tempprime!=0)
      setPrime(i);
    else
      setFactor(i, tempprime);
  }
}

int Primes::smallestFactor(int num) {
  intvector::iterator p=primes.begin();    

  while ((num>=(*p)*(*p) && p!=primes.end())) {
    if (num % (*p)==0)
      return *p;
    p++;
  }
 
  return num;
}

bool Primes::isPrime(int num) {
  if (num>=factor.size()) {
    return num==smallestFactor(num);
  } else {
    return num==factor[num];
  }
}

void Primes::getZeisels(intvector& dest, int A, int B) {
  if (A+B==0) return;

  int currentFactor=A+B;
  int newFactor=0;
  
  double fullNumber=currentFactor;
  
  if (!isPrime(currentFactor)) return;

  currentFactor=A*currentFactor+B;
  fullNumber*=currentFactor;
  
  if (!isPrime(currentFactor)) return;

  newFactor=A*currentFactor+B;
  if ((newFactor-B)/A!=currentFactor)
    return;
  currentFactor=A*currentFactor+B;
  
  fullNumber*=currentFactor;
  
  while (isPrime(currentFactor) && (fullNumber<=2000000000.0)) {
    int intFull = (int) fullNumber;
    dest.push_back(intFull);
    newFactor=A*currentFactor+B;

    if ((newFactor-B)/A!=currentFactor)
      return;

    currentFactor=newFactor;
    fullNumber*=currentFactor;
  }
};

int nLess(intvector& zeiselNumbers, int x) {
  int i=0;
  while (i<zeiselNumbers.size() && zeiselNumbers[i]<x) i++;
  return i;
}

int main() {
  Primes b(65536);
  intvector zeiselNumbers;
  
  for (int i=1; i<700; i++) {
     for (int j=(1-i); j<1300-i; j++)
       b.getZeisels(zeiselNumbers,i,j);
  }

  sort(zeiselNumbers.begin(),zeiselNumbers.end());

  int N;
  int xL, xH;
  cin >> N;
  for (int i=0; i<N; i++) {
    cin >> xL >> xH;
    cout << nLess(zeiselNumbers,xH+1)-nLess(zeiselNumbers,xL) << endl;
  }
}