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

using namespace std;



int dp[100009], total[100009];

int store[100009], mark[100009], nPrime, isPrime[100009];



///seieve

void seive(int n)

{

    int i,j, lim = sqrt(n*1.0) +2;



    mark[1] = 1;

    for(i = 4; i<=n; i+=2) mark[i] = 1;



    store[nPrime++] = 2;



    isPrime[2] = 1;



    for(i=3; i<=n; i+=2)

    {

        if(!mark[i])

        {

            store[nPrime++] = i;

            isPrime[i] = 1;



            if(i<=lim)

            {

                for(j=i*i; j<=n; j+=i*2)

                {

                    mark[j]=1;

                }

            }

        }

    }





}



int f(int n) /// is like 2017

{

    if(dp[n]!=-1) return dp[n];

    if(n%2==0) return dp[n] = 0;

    if(isPrime[n]==1 && isPrime[ (n+1)/2 ]==1) return dp[n] = 1;

    else return dp[n] = 0;

}



void cnt(int N)

{

    for(int i=0; i<=N; i++) f(i);

    total[1] = 0;

    for(int i=2; i<=N; i++)

    {

        total[i] = total[i-1]+dp[i];

    }

}



int main()

{

    int q;

    int l, r;

    int ans = 0;



    seive(100002);

    memset(dp,-1,sizeof(dp));

    cnt(100002);



    //for(int i=0; i<nPrime; i++) cout<<store[i]<<" ";

    //for(int i=0; i<100000; i++) if(dp[i]) cout<<i<<" "<<total[i]<<" "<<endl;



    cin>>q;

    while(q--)

    {

        cin>>l>>r;

        if(l==1) ans = total[r];

        else ans = total[r] - total[l-2];

        cout<<ans<<endl;

    }



    //main();





    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.680167167870292x):
#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;

}