// 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.3246290636944982x):
#include <bits/stdc++.h>



using namespace std;



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

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

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

#define FOREACH(x,a) for(auto& (x) : (a))

#define mp make_pair

#define All(a) (a).begin(), (a).end()

template <typename T=int>

inline T IN(){T x; cin>>x; return(x);}

inline void CIN(){}

template <class Head,class... Tail>

inline void CIN(Head&& head,Tail&&... tail){

    cin>>head;

    CIN(move(tail)...);

}

#define CINT(...) int __VA_ARGS__;CIN(__VA_ARGS__)

#define LCIN(...) ll __VA_ARGS__;CIN(__VA_ARGS__)

#define SCIN(...) string __VA_ARGS__;CIN(__VA_ARGS__)



typedef long long ll;

typedef vector<int> V;

typedef vector<ll> VL;

typedef pair<int,int> P;

typedef pair<ll,ll> PL;

typedef priority_queue<int> PQ;

typedef priority_queue<int,V,greater<int>> PQG;



const int INF = 1e9;

const int MOD = 1e9+7;

const ll LINF = 1e18;



int Q;

const int rmax=1e5;

bool is_prime[rmax+1];

int prime[rmax+1];

int prisum[rmax+1];



int sieve(int n){

    int p=0;

    REP(i,n+1) is_prime[i]=true;

    is_prime[0]=is_prime[1]=false;

    REP(i,n+1){

        if(is_prime[i]==true){

            prime[p++]=i;

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

                is_prime[j]=false;

            }

        }

    }

    return p;

}



int main(){

    cin>>Q;

    sieve(rmax);

    REP(i,rmax+1){

        if(is_prime[i]==true && is_prime[(i+1)/2]==true){

            prisum[i]=1;

        }

    }

    FOR(i,1,rmax+1){

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

    }

    REP(i,Q){

        CINT(l,r);

        cout<<prisum[r]-prisum[l-1]<<"\n";

    }

    return 0;

}