#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

//-------------------------------------------------
//--Sieve of Eratosthenes
//-------------------------------------------------
class Sieve
{
private:
    ::std::vector<bool> prime;
public:
    Sieve(int n):prime(n+1, true){
        prime[0] = prime[1] = false;
        for(int i=2; i*i<=n; i++){
            if (!prime[i]) continue;
            for(int j=i*2; j<=n; j+=i){
                prime[j] = false;
            }
        }
    }
    bool isprime(int x){return prime[x];}
};

//-------------------------------------------------
//--Range Set Counter
//-------------------------------------------------
template<typename T>
class RangeSet
{
private:
    ::std::vector<int> v;
    ::std::unordered_map<T, int> Map;
    ::std::vector<::std::vector<int> > data;
    int kind;
public:
    RangeSet(const ::std::vector<T> &v_):v(v_.size()){
        int sz = v_.size(); kind = 0;
        for(int i=0;i<sz;i++){
            T t = v_[i];
            if (Map.count(t)){
                data[Map[t]].push_back(i);
            }else{
                Map[t] = kind++;
                data.push_back(::std::vector<int>());
                data.back().push_back(i);
            }
            v[i] = Map[t];
        }
    }
    //query for all elements
    int query(T x){
        if (!Map.count(x)) return 0;
        return data[Map[x]].size();
    }
    //query for [a, b]
    int query(int a, int b, T x){
        if (a>b) return 0;
        if (!Map.count(x)) return 0;
        int xi = Map[x];
        auto right = ::std::upper_bound(data[xi].begin(),data[xi].end(),b);
        auto left  = ::std::lower_bound(data[xi].begin(),data[xi].end(),a);
        return right-left;
    }
    //search x for [k, tail]
    int find(int k, T x){
        if (!Map.count(x)) return -1;
        int xi = Map[x];
        auto itr = ::std::lower_bound(data[xi].begin(),data[xi].end(),k);
        if (itr!=data[xi].end()){
            return *itr;
        }else{
            return -1;
        }
    }
    //update for one point
    void update(int k, T x){
        int ei = v[k];
        auto eitr = ::std::lower_bound(data[ei].begin(),data[ei].end(),k);
        data[ei].erase(eitr);
        v[k] = Map[x];
        if (Map.count(x)){
            int xi = Map[x];
            auto itr = ::std::lower_bound(data[xi].begin(),data[xi].end(),k);
            data[xi].insert(itr, k);
        }else{
            Map[x] = kind++;
            data.push_back(::std::vector<int>());
            data.back().push_back(k);
        }
    }
};

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int q; cin>>q;
    Sieve sieve(100010);
    vector<bool> ok(100010, false);
    FOR(i,1,100010){
        if (sieve.isprime(i) && sieve.isprime((i+1)/2)){
            ok[i] = true;
        }
    }
    RangeSet<bool> rs(ok);
    while(q--){
        int l,r; cin>>l>>r;
        cout<<rs.query(l,r,true)<<endl;
    }
    return 0;
}


Measured memory_bytes: 1528