// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)

#define REPR(i, n) for(int i = n - 1; i >= 0; i--)

#define FOR(i, m, n) for(int i = m; i <= n; i++)

#define FORR(i, m, n) for(int i = m; i >= n; i--)

#define SORT(v, n) sort(v, v+n);

#define VSORT(v) sort(v.begin(), v.end());

 

using ll = long long;

using vll = vector<ll>;

using vvll = vector<vector<ll>>;

using P = pair<ll, ll>;



vll Eratosthenes(ll N){

    vll a(N + 1, 1);

  	for(ll i = 0; i < N; i++){

		a[i] = 1;

	}

	for(ll i = 2; i < sqrt(N); i++){

		if(a[i]){

			for(ll j = 0; i * (j + 2) < N; j++){

				a[i *(j + 2)] = 0;

			}

		}

	}

    a[0] = a[1] = 0;

    return a;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    ll q;

    cin >> q;

    ll l, r;



    vll isprime = Eratosthenes(1e5 + 10);

    vll sss(1e5 + 11);

    REP(i, 1e5 + 10){

        if(i == 0) continue;

        sss[i] = sss[i - 1] + isprime[i] * isprime[(i + 1) / 2];

    }

    while(q){

        cin >> l >> r;

        ll res = sss[r] - sss[l - 1];

        cout << res << endl;

        q--;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.9374779185790594x):
#include <bits/stdc++.h>

using namespace std;



#define df(b, e) ((b) > (e))

#define fore(i, b, e) for(auto i = (b) - df(b, e); i != e - df(b, e); i += 1 - 2 * df(b, e))

#define sz(x) (int) x.size()

#define all(x) x.begin(), x.end()

#define f first

#define s second

#define pb push_back



typedef long long lli;

typedef long double ld;

typedef pair<int, int> ii;



template <class T>

struct rge { T b, e; };



template <class T>

rge<T> range(T i, T j) {

  return rge<T>{i, j};

}



template <class T> auto dud(T *x) -> decltype(cerr << *x, 0);

template <class T> char dud(...);



struct debug {

#ifdef LOCAL

  ~debug() { cout << endl; }



  template <class T>

  typename enable_if<sizeof dud<T>(0) != 1, debug &>::type operator << (T i) {

    cout << boolalpha << i;

    return *this;

  }



  template <class T>

  typename enable_if<sizeof dud<T>(0) == 1, debug &>::type operator << (T i) {

    return *this << range(begin(i), end(i));

  }



  template <class A, class B>

  debug & operator << (pair<A, B> d) {

    return *this << "(" << d.first << ", " << d.second << ")";

  }



  template <class T>

  debug & operator << (rge<T> d) {

    *this << "[";

    for (auto it = d.b; it != d.e; ++it)

      *this << ", " + 2 * (it == d.b) << *it;

    return *this << "]";

  }

#else

  template <class T> 

  debug & operator << (const T&) {

    return *this; 

  }

#endif

};



#define deb(...) " " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " "



const int N = 1e5 + 5;



bitset<N> isp;

int sim[N];

int q, l, r;



int main() {

  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  isp.set();

  isp[0] = isp[1] = 0;

  fore (i, 2, N) {

    if (isp[i]) {

      sim[i] += isp[(i + 1) / 2];

      if (1LL * i * i < N)

        for (int j = i * i; j < N; j += i)

          isp[j] = 0;

    }

    sim[i] += sim[i - 1];

  }

  cin >> q;

  while (cin >> l >> r) 

    cout << sim[r] - sim[l - 1] << '\n';

  return 0;

}