#include<bits/stdc++.h>
using namespace std;
#define si(x) scanf("%d",&x)
#define RANGE 200005
bool check[100006];
bool isprime(int n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    else if(n%2==0) return 0;
    else if(n&1)
    {
        for(int i=2; i<=sqrt(n); i++)
            if(n%i==0) return 0;
    }
    return 1;
}
void pre()
{
    check[2]=1,check[1]=0;
    memset(check,0,sizeof check);
    for(int i=3; i<100004; i++) if(isprime(i)) check[i]=1;
}
int main()
{
    pre();
    int q;
    cin>>q;
    while(q--)
    {
        int l,r,c=0;
        cin>>l>>r;
        for(int i=l; i<=r; i++)
            if(check[i] && check[(i+1)/2]) c++;
        cout<<c<<endl;
    }
}
