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

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int INF = 1e9;

const ll LINF = 1e18;



/*

<url:https://abc084.contest.atcoder.jp/tasks/abc084_d>

問題文============================================================

 「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。

 

 Q 個のクエリが与えられます。

 

 クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、

 li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。

=================================================================



解説=============================================================



 1..N までに2017素数であるものの個数を累積和で確保しておき

 一つのキューに対して O(1) でもとまる

 

================================================================

*/

const ll MAX_PRIME = 100000;

vector<int> primes(MAX_PRIME + 1);

vector<int> is_prime(MAX_PRIME + 1,true);

vector<int> prime2017(MAX_PRIME + 1,0);

vector<int> cusum(MAX_PRIME + 1,0);

void init_primes(){

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

    for(int i = 2; i <= MAX_PRIME;i++){

        if(is_prime[i]){

            primes.push_back(i);

            for(int j = i*2; j <= MAX_PRIME; j+=i) is_prime[j] = false;

        }

    }

}



void init(){

    init_primes();

    for(int i = 1; i <= MAX_PRIME; i++){

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

            prime2017[i] = true;

        }

    }

    for(int i = 0; i < MAX_PRIME;i++){

        cusum[i+1] = cusum[i] + prime2017[i+1];

    }

}

int main(void) {

	cin.tie(0); ios::sync_with_stdio(false);

    init();

    ll Q; cin >> Q;

    while(Q--){

        ll l,r; cin >> l >> r;

        cout << cusum[r] - cusum[l-1] << endl;

    }

	return 0;

}


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

}