// 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.247524316140235x):
/*

                  友利奈緒ぱわーでACしてくれ！！！！！！！！！！！！

                  Charlotteまだ見てない人は見ような！！！！！！！



                  ／　 /:／　　　　　　　　　　　 　 ＼:ヽ　＼

  　　　　　　　 /　　／　　　　　　 　 　 　 　 　 　 　 ＼　　ヽ

  　　　　　＼__L 彡　　　　　　　　　　　　　　　　　　　 ヽ　　',

  　　　　　　　ﾌ /　　　/　　/　 /　　　,　　 　 　 　 ヽ　　', 　ｊ

  　　　　　　　ﾚ　　　 /　　/ 　/　 　 　 　 　 　 　 　 ', 　ヽ　j

  　　　 　 　 // 　 　 !　/_l＿/__ノ 　　{ ＼}　　　　 　 ',　　',/

  　　　　　　i ﾊ 　 　 {　从j　ﾊ　i　　　 ',　 ト-､}　 i i　 }　　jj

  　　　　　　( ﾊ　　　(　 川　ハ ﾊ　 !　 '　ﾊ　 ﾊ　j j　,' 　 八

  　　　 ＜＿,ｨ∧　　　斗芹ﾃミxハ ﾊ　 ﾚ　} /__ﾚﾚ　/ 　 ∧ ＼　ﾉ

  　　　 　 　 ∨　＼ 　ゝ　辷:ソ　　 　)　芹ﾚ心ヾレ′　/ ト--　´

  　　　＼ｰ‐'　ﾉ　　 ＼ゝ　　　　　　 　 　 ゞ:_ソ "/ 　／ 　ヽ

  　　　　 　 フ　　　　i八 " "　　　,　　　　　　　ム彡　　　　＼

  　　　　 　/　　/　　j　 ト　　　　　　 　 　 " "イト＜　 　 　 ＼＼

  　　　　 /　　/　　　j　/／ヽ､ 　 ∩　　 　 イ　{ {　　￣ フフへ ＼＼

  　　　　(　／　　　 ,/ / 　　i　＞――＜ニニニﾆ┐　 〃／: : ヽ　ヽヽ

  　　　　／　　ィT´/ /┌―　￣￣ /::: , ,)　 　 　 〃／／: : : : : :}　ヽヽ)

  　　　/ /　 ∧ヾi┌― { {￣　　　 ﾉ:::トﾟ<　 　 　 ∥//: : : : : : : : i　 ﾉ ﾉ

  . 　　( 人　 {:ヽヾi∨　∧V　　　 /:::/　､ヽ　　　 ∥/: : : : : : : : : :}　/

  　　　V　( ∧: :＼'∨　∧V　　 ﾉ:::/　 ∧ 〉＿__∥: : : : : :／: : : :ﾚ

  　　 　 　 /∧: : : : ∨　∧V┬ｲ:::ﾉ　 〈 TT　|　|{{: : : : ／: : : : : ∧　　 ﾉ

  　　　 　 (　ハ: : : : :∨'T∧Vi　i (　 　 V　!　!　{{: : ／ : : : : : : /　ｰ　ノ

  　　　　　V　ハ: : : : :∨ﾍ∧V　i ゝゝ　 i／⌒＼{／ : : : : : : : /ｰ― ´

  　　　　　 ∨　ヽ: : : : :∨ﾍ∧∨i　〉 〉 /　/二　 ): : : : : : : : :/



          (https://seesaawiki.jp/asciiart/d/Charlotte より)

*/

#include <bits/stdc++.h>

using namespace std;

using ll = long long; using ull = unsigned long long;

// #define int ll

// #define DEBUG 42

inline void nprint(){}

template <class Head, class... Tail>

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

    cout << head << endl;

    nprint(move(tail)...);

}

#ifdef DEBUG

  #define eprint(...) nprint(__VA_ARGS__)

#else

  #define eprint(...) if(0==1) cout << 1 << endl;

#endif

#define Yes(a) cout << (a ? "Yes" : "No") << endl

#define YES(a) cout << (a ? "YES" : "NO") << endl

#define POSSIBLE(a) cout << (a ? "POSSIBLE" : "IMPOSSIBLE") << endl

using cmp = complex<double>;

using vb = vector<bool>; using vvb = vector<vb>;

using vi = vector<int>; using vvi = vector<vi>;

using vl = vector<ll>; using vvl = vector<vl>;

template<class T> using V = vector<T>;

template<class T> using VV = vector<V<T>>;

#define fi first

#define se second

#define maxs(x,y) (x=max(x,y))

#define mins(x,y) (x=min(x,y))

using pii = pair<int,int>; using pll = pair<ll,ll>;

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

#define REP(i,n) FOR(i,0,n)

#define FORS(i,a,b) FOR(i,a,b+1)

#define REPS(i,n) REP(i,n+1)

#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)

#define RREP(i,n) RFOR(i,0,n)

#define RREPS(i,n) RREP(i,n+1)

#define RFORS(i,a,b) RFOR(i,a,b+1)

#define ALL(obj) (obj).begin(), (obj).end()

#define RALL(obj) (obj).rbegin(), (obj).rend()

#define PERM(c) sort(ALL(c)); for(bool cp = true;cp;cp = next_permutation(ALL(c)))

#define eb(val) emplace_back(val)

constexpr double PI = acos(-1), EPS = 1e-10;

constexpr ll MOD = 1E9+7;

constexpr int dx[] = {1,0,-1,0}; constexpr int dy[] = {0,1,0,-1};

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p){

  return s << "(" << p.first << ", " << p.second << ")";

}

template<class T> istream& operator>>(istream &is,vector<T> &st){

  for(size_t i=0;i<st.size();++i) is >> st[i];

  return is;

}

template<class T> istream& operator>>(istream &is,vector<vector<T>> &st){

  for(size_t i=0;i<st.size();++i) is >> st[i];

  return is;

}

template<class T> ostream& operator<<(ostream &os, const vector<T> &st){

  for(size_t i=0;i<st.size();++i){

    if(i==st.size()-1) os << st[i];

    else os << st[i] << " ";

  }

  return os;

}

template<class T> ostream& operator<<(ostream &os, const vector<vector<T>> &st){

  for(size_t i=0;i<st.size();++i){

    os << st[i];

    if(i!=st.size()-1) os << endl;

  }

  return os;

}

pair<vl,vb> eratosthenes_sieve(ll n){

  vb is_prime(n+1,true);

  vl prime;

  is_prime[0] = false;

  is_prime[1] = false;

  FOR(i,2,sqrt(n)+1){

    if(!is_prime[i]) continue;

    for(ll j=2*i;j<=n;j+=i) is_prime[j] = false;

    prime.eb(i);

  }

  FOR(i,sqrt(n)+1,n+1){

    if(is_prime[i])prime.eb(i);

  }

  return {prime,is_prime};

}

signed main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

  cout << fixed << setprecision(10);

  int q;

  cin >> q;

  auto lst = eratosthenes_sieve(100005).se;

  vi sum(100005,0);

  FOR(i,1,100001){

    if(i%2&&lst[i]&&lst[(i+1)/2]) sum[i] = sum[i-1]+1;

    else sum[i] = sum[i-1];

  }

  REP(i,q){

    int l,r;

    cin >> l >> r;

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

  }

}