//#define dalao
//#include <bits/stdc++.h>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <cassert>
#include <iterator>
#include <complex>
#include <cstdarg>
using namespace std;
#define    FOR(i,a,n)       for(register int i=a;i<=n;++i)
#define    FIR(i,n,a)       for(register int i=n;i>=a;--i)
#define    VOR(i,a)         for(register int i=0,n=a.size();i<n;++i)
#define    VIR(i,a)         for(register int i=a.size()-1;i>=0;++i)
#define    SOR(i,a)         for(register auto i=a.begin();i!=a.end();++i)
#define    all(a)           (a).begin(),(a).end()
#define    vlb(a,n)         (lower_bound(all(a),n)-a.begin())
#define    vub(a,n)         (upper_bound(all(a),n)-a.begin())
#define    mem(a,b)         memset(a,b,sizeof(a))
#define    sz(a)            (a.size())
#define    pw(x)            (1ll<<(x))
#define    lowbit(x)        ((x)&(-x))
#define    bug              puts("\nH");
#pragma    comment(linker, "/STACK:1024000000,1024000000")
#define    IOS              ios::sync_with_stdio(false)
#define    getmid           mid=l+r>>1
#define    lch              p<<1,l,mid
#define    rch              p<<1|1,mid+1,r
#define    ll               p<<1
#define    rr               p<<1|1
#define    queue_           priority_queue
#define    pb               push_back
#define    mp               make_pair
#define    lb               lower_bound
#define    ub               upper_bound
#define    ff               first
#define    ss               second
typedef    long long        LL;
typedef    long double      ld;
typedef    pair<double,int> db;
typedef    pair<int,int>    PII;
typedef    pair<LL,LL>      PLL;
typedef    vector<int>      VI;
typedef    vector<LL>       VLL;
typedef    vector<PII>      VPII;
typedef    vector<PLL>      VPLL;
const int           dx[]= { 0, 1, 0,-1, 0, 1,-1, 1,-1};
const int           dy[]= {-1, 0, 1, 0,-1, 1,-1,-1, 1};
const LL            LINF=0xfcfcfcfcfcfcfcfll;
const long double   pi=3.141592653589793238462643383279502881l;
const double        ee=2.718281828459;
const double        eps=0.00000001;
const int           INF=0x3f3f3f3f;
const int           MOD=1000000007;
const char          hr='\n';
const char          kb=' ';
inline LL powmod(LL x,LL n,LL mod=MOD,LL res=1) { for(; n; x=x*x%mod,n>>=1)if(n&1)res=res*x%mod; return res; }
template<typename T>inline T max(T a,T b,T c) { return max(a,max(b,c)); }
template<typename T>inline T min(T a,T b,T c) { return min(a,min(b,c)); }
template<typename T>inline T max(T a,T b,T c,T d) { return max(a,max(b,c,d)); }
template<typename T>inline T min(T a,T b,T c,T d) { return min(a,min(b,c,d)); }
inline int mul10(int n) { return (n<<3)+(n<<1); }
inline LL mul10(LL n) { return (n<<3)+(n<<1); }
inline int div10(int n,int q=0) { q=(n>>1)+(n>>2),q+=(q>>4),q+=(q>>8),q+=(q>>16),q>>=3; return q+(n-mul10(q)>9); }
inline LL div10(LL n,LL q=0) { q=(n>>1)+(n>>2),q+=(q>>4),q+=(q>>8),q+=(q>>16),q+=(q>>32),q>>=3; return q+(n-mul10(q)>9); }
static char bfi[1000000],*ci=bfi-1,*cl=bfi-1,bfo[1000000],*co=bfo-1,chr;
inline bool dig() { return (chr>='0'&&chr<='9')?1:0; }
inline char gtc() { return ci==cl&&(cl=(ci=bfi-1)+fread(bfi,1,1000000,stdin),ci==cl)?EOF:*++ci; }
inline void readbit(double &ret,double bit=0.1) { if(chr=gtc(),dig())ret+=(chr-'0')*bit,readbit(ret,bit*0.1); }
inline bool _read(int &res,bool flag=0,int sum=0) { while(chr=gtc(),!(dig()||(chr=='-'?(chr=gtc(),flag=1):0))) if(chr==-1) return 0; while(dig())sum=mul10(sum)+chr-'0',chr=gtc(); return (res=flag?-sum:sum,1); }
inline bool _read(LL &res,bool flag=0,LL sum=0) { while(chr=gtc(),!(dig()||(chr=='-'?(chr=gtc(),flag=1):0))) if(chr==-1) return 0; while(dig())sum=mul10(sum)+chr-'0',chr=gtc(); return (res=flag?-sum:sum,1); }
inline bool _read(double &ret,bool flag=0,LL sum=0) { while(chr=gtc(),!(dig()||(chr=='-'?(chr=gtc(),flag=1):0))) if(chr==-1) return 0; while((dig()))sum=mul10(sum)+chr-'0',chr=gtc(); if(ret=sum,chr=='.')readbit(ret); return (ret=flag?-ret:ret,1); }
inline bool _read(char &ch) { while(chr=gtc(),chr==' '||chr=='\n'||chr=='\t') if(chr==-1) return 0; return (ch=chr,1); }
inline bool _read(char *p) { while(chr=gtc(),chr==' '||chr=='\n'||chr=='\t') if(chr==-1) return 0; while(chr!='\n'&&chr!=EOF)*p++=chr,chr=gtc(); return (*p=0,1); }
inline void _scan(int &x) { scanf("%d%*c",&x); }
inline void _scan(LL &x) { scanf("%I64d%*c",&x); }
inline void _scan(double &x) { scanf("%lf%*c",&x); }
inline void _scan(char &ch) { scanf("%c%*c",&ch); }
inline void _scan(char *p) { scanf("%s%*c",p); }
inline void _debug(int x) { printf(" %d",x); }
inline void _debug(LL x) { printf(" %I64d",x); }
inline void _debug(double x) { printf(" %.6f",x); }
inline void _debug(const char ch) { printf(" %c",ch); }
inline void _debug(const char *p) { printf(" %s",p); }
inline void _write() { fwrite(bfo,1,co-bfo+1,stdout),co=bfo-1; }
inline void ptc(char ch) { if(*++co=ch,co==bfo+999999)_write(); }
inline void _out(int x) { if(x<0)ptc('-'),x=-x; if(x>9)_out(div10(x)); ptc(x%10+'0'); }
inline void _out(LL x) { if(x<0)ptc('-'),x=-x; if(x>9)_out(div10(x)); ptc(x%10+'0'); }
inline void _out(double x,int n=6) { if(x<0)ptc('-'),x=-x; _out((LL)x),x-=(LL)x,ptc('.'); while(n--)x*=10; _out(LL(x+0.5)); }
inline void _out(db x) { _out(x.ff,x.ss); }
inline void _out(const char ch) { ptc(ch); }
inline void _out(const char *p) { while(*p)ptc(*p++); }
#ifndef dalao
inline void scan() {}
template<class T,class... U>inline void scan(T &head,U &...tail) { _scan(head); scan(tail...); }
inline void read() {}
template<class T,class... U>inline void read(T &head,U &...tail) { _read(head); read(tail...); }
inline void debug() {}
template<class T,class... U>inline void debug(T head,U ...tail) { _debug(head); debug(tail...); }
inline void out() {}
template<class T,class... U>inline void out(T head,U ...tail) { _out(head); out(tail...); }
#else
#define read(x) _read(x)
#define scan(x) _scan(x)
#endif
/**_________________________head.end__________________________**/

const int N=100005;
bool prime[N];
int b[N];

void IsPrime(){
     prime[0]=prime[1]=0;prime[2]=1;
     for(int i=3;i<N;i++)
        prime[i]=i%2==0?0:1;
     int t=(int)sqrt(N*1.0);
     for(int i=3;i<=t;i++)
       if(prime[i])
         for(int j=i*i;j<N;j+=2*i)//优化
            prime[j]=0;
}

/**_______________________main().begin________________________**/
int main() {
    IOS;
#ifndef file__
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif   ///main code begin......
    int q,l,r,i=1;
    IsPrime();
    FOR(i,2,100000)if(prime[i]&&prime[i+1>>1])b[i]=1;
    FOR(i,2,100000)b[i]+=b[i-1];
//    FOR(i,1,10)cout<<b[i]<<endl;
    cin>>q;
    while(q--) {
        cin>>l>>r;
        cout<<b[r]-b[l-1]<<endl;
    }
#ifndef out__   ///code end......
    _write();
#endif
    return 0;
}
/**________________________main().end_________________________**/

/***************************************************************
**                                                            **
**  *********   *********   ********    **          ********* **
**      **      **          **     **   **          **        **
**      **      **          **     **   **          **        **
**      **      *********   ********    **          ********* **
**      **      **          **     **   **          **        **
**      **      **          **     **   **          **        **
**      **      *********   ********    *********   ********* **
**                                                            **
***************************************************************/


Measured memory_bytes: 1152