#include <iostream>
#include <vector>
using namespace std ;
vector<char> sieve ;
int main() {
   vector<pair<int, int>> r ;
   int f, n, hi=10 ;
   cin >> n ;
   vector<int> a(n), b(n) ;
   for (int i=0; i<n; i++) {
      cin >> a[i] >> b[i] ;
      hi = max(hi, b[i]) ;
   }
   sieve.resize(hi+1) ;
   for (int i=2; i<=hi; i += 2)
      sieve[i] = 1 ;
   for (f=3; f<=hi; f += 2)
      if (sieve[f] == 0)
         for (int j=f; j<=hi; j += f)
            sieve[j]++ ;
   vector<int> g(hi+1) ;
   int s = 0 ;
   for (int i=0; i<=hi; i++)
      g[i] = (s += 1 - 2 * (sieve[i] & 1)) ;
   for (int i=0; i<n; i++)
      cout << g[b[i]] - g[a[i]-1] << endl ;
}