#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
/*int n,m,cnt[maxn];
int main(){
    while (~scanf("%d%d",&n,&m)){
        memset(cnt,0,sizeof(cnt));
        int mx=0;
        for (int i=1;i<=n;i++){
            int l,r;read(l),read(r);
            cnt[l]++,cnt[r+1]--;
        }
        for (int i=1;i<=5000;i++) mx=max(mx,cnt[i]+=cnt[i-1]);
        printf("%d\n",mx/m+(mx%m==0?0:1));
    }
    return 0;
}*/
/*int cnt[10];
char s[maxn];
int main(){
    scanf("%s",s);
    int len=strlen(s);
    for (int i=0;i<len;i++){
        cnt[s[i]-'0']++;
    }
    int x=0;
    for (int i=0;i<10;i++){
        if (cnt[i]) x++;
    }
    if (x==1) puts("YES");
    else puts("NO");
    return 0;
}*/
/*int m,pos[26],pos2[26];
char x[2],y[2];
char s[maxn];
int main(){
    while (~scanf("%s",s)){
        int len=strlen(s);
        for (int i=0;i<26;i++) pos[i]=i,pos2[i]=i;
        for (read(m);m--;){
            scanf("%s%s",x,y);
            int xxx=pos2[x[0]-'a'],yyy=pos2[y[0]-'a'];
            //swap(pos[xxx],pos[yyy]);
            pos2[x[0]-'a']=yyy,pos2[y[0]-'a']=xxx;
        }
        for (int i=0;i<len;i++){
            putchar(pos[pos2[s[i]-'a']]+'a');
        }
        puts("");
    }
    return 0;
}*/
/*string s="gu...";
string t="The story is so boring. And I am so hungry!" ;
int main(){
    int n;
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++) cout<<s;
        cout<<endl;
        cout<<t<<endl;
    }
    return 0;
}*/
/*ll dp[22][2];
int main(){
    dp[1][0]=1;
    dp[1][1]=1;
    for (int i=2;i<=20;i++){
        dp[i][0]=dp[i-1][1];
        dp[i][1]=dp[i-1][0]+dp[i-1][1];
    }
    int n;
    while (~scanf("%d",&n)){
        cout<<dp[n][0]+dp[n][1]<<endl;
    }
    return 0;
}*/
/*int n;
char x[20],y[20];
int main(){
    while (~scanf("%d",&n)){
        int a=0,b=0;
        for (int i=1;i<=n;i++){
            scanf("%s%s",x,y);
            if (x[0]=='J' && y[0]=='M') a+=3;
            else if (x[0]=='M' && y[0]=='T') a+=3;
            else if (x[0]=='T' && y[0]=='S') a+=3;
            else if (x[0]=='S' && y[0]=='H') a+=3;
            else if (x[0]=='H' && y[0]=='J') a+=3;
            else if (y[0]=='J' && x[0]=='M') b+=3;
            else if (y[0]=='M' && x[0]=='T') b+=3;
            else if (y[0]=='T' && x[0]=='S') b+=3;
            else if (y[0]=='S' && x[0]=='H') b+=3;
            else if (y[0]=='H' && x[0]=='J') b+=3;
            else a++,b++;
        }
        if (a>b) puts("Alice");
        else if (a==b) puts("Draw");
        else puts("Bob");
    }
    return 0;
}*/
/*struct Node{
    int a,b;
}can[100005];
inline bool cmp1(Node&a,Node&b){
    if (a.a-a.b==b.a-b.b) return a.b<b.b;
    return a.a-a.b>b.a-b.b;
}
inline bool cmp2(Node&a,Node&b){
    if (a.b-a.a==b.b-b.a) return a.a<b.a;
    return a.b-a.a>b.b-b.a;
}
int main(){
    int n,k;
    while (~scanf("%d%d",&n,&k)){
        for (int i=1;i<=n;i++) read(can[i].a);
        for (int i=1;i<=n;i++) read(can[i].b);
        sort(can+1,can+1+n,cmp1);
        ll ans=0,ans2=0;
        for (int i=1;i<=k;i++){
            ans+=can[i].a*1LL;
        }
        for (int i=k+1;i<=n;i++){
            ans+=can[i].b*1LL;
        }
        sort(can+1,can+1+n,cmp2);
        for (int i=1;i<=n-k;i++){
            ans2+=can[i].b*1LL;
        }
        for (int i=n-k+1;i<=n;i++){
            ans2+=can[i].a*1LL;
        }
        cout<<max(ans,ans2)<<endl;
    }
    return 0;
}*/
/*int n,m,q;
int cnt[maxn][maxn];
char maze[1005][1005];
int main(){
    read(n),read(m),read(q);
    for (int i=1;i<=n;i++){
        scanf("%s",maze[i]+1);
        for (int j=1;j<=m;j++){
            if (maze[i][j]=='#') cnt[i][j]++;
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cnt[i][j]+=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
        }
    }
    for (;q--;){
        int i,j;char op[2];scanf("%d%d%s",&i,&j,op);
        int ans=0;
        if (op[0]=='L'){
            ans+=cnt[i][j]-cnt[i-1][j];
        }
        else if (op[0]=='R'){
            ans+=cnt[i][m]-cnt[i-1][m]-cnt[i][j-1]+cnt[i-1][j-1];
        }
        else if (op[0]=='U'){
            ans+=cnt[i][j]-cnt[i][j-1];
        }
        else ans+=cnt[n][j]-cnt[n][j-1]-cnt[i-1][j]+cnt[i-1][j-1];
        if (ans==0) puts("YES");
        else puts("NO");
    }
    return 0;
}*/
/*int n;
int cnt[13][13]={1,1,1,1,1,1,1,1,1,1,1,1,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,3,3,4,4,4,3,3,2,2,1,
                 1,2,2,3,3,4,4,4,3,3,2,2,1,
                 1,2,2,3,3,4,4,4,3,3,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,1,1,1,1,1,1,1,1,1,1,1,1};
char s[14][14];
int main(){
    while (~scanf("%d",&n) && n){
        double ans=0;
        for (int i=0;i<13;i++){
            scanf("%s",s[i]);
            for (int j=0;j<13;j++){
                ans+=(s[i][j]=='#'?cnt[i][j]*1.0:0);
            }
        }
        printf("%.2lf\n",ans/n);
    }
    return 0;
}*/
/*const int N=10005;
int n;
ll w[N];
int main(){
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++) read(w[i]),w[i]+=w[i-1];
        int m,L,R;
        ll ans=0;
        for (read(m);m--;){
            read(L),read(R);
            ans+=max(0LL,w[R]-w[L-1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}*/
/*const ll MOD=1000000007LL;
ll n,m;
ll ksm(ll a,ll n){
    if (a<0) a+=P;
    if (n<0) n+=P;
    ll res=1LL;
    while (n){
        if (n&1) res=res*a%P;
        a=(a*a)%P;
        n>>=1;
    }
    return res;
}
int main(){
    read(n),read(m);
    m%=MOD;
    cout<<((ksm(m,n)-m*ksm(m-1,n-1)%P)%P+P)%P<<endl;
    return 0;
}*/
const int N=1e5;
bool vis[N+5];
int cnt[N+5],primes[N+5];
void init(){
    for (int i=2;i<=N;i++){
        if (!primes[i]) primes[++primes[0]]=i,vis[i]=true;
        for (int j=1;j<=primes[0] && primes[j]*i<=N;j++){
            primes[primes[j]*i]=1;
            if (i%primes[j]==0) break;
        }
    }
}
int main(){
    int Q;
    init();
    for (int i=1;i<=N;i++) cnt[i]=cnt[i-1]+(vis[i]&&vis[(i+1)/2]?1:0);
    for (read(Q);Q--;){
        int l,r;read(l),read(r);
        printf("%d\n",cnt[r]-cnt[l-1]);
    }
    return 0;
}


Measured memory_bytes: 1536