// 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.7001455783319024x):
#include <bits/stdc++.h>



using namespace std;



#define sq(a) ((a) * (a))

#define all(x) (x).begin(), (x).end()

#define pb push_back

#define mp(a, b) make_pair(a, b)

#define what_is(x) cerr << fixed << setprecision(2) << #x << " = " << x << endl

#define setbitj(n, j) (n |= (1 << (j)))

#define isbitjOn(n, j) (((n & (1 << (j))) > 0) ? 1 : 0)

#define safeMod(a, m) ((((a)%(m))+(m))%(m))/*handling negative sign of remainder*/



typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef vector<int> vi;

typedef vector<pii> vii;



const double EPS = 1e-9;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

const int MAX = 100005;

const int MOD = 1000000007;



inline bool isEq(double a, double b){return abs(a - b) < EPS;}

inline double toRad(double deg){return deg*PI/180;}

inline double toDeg(double rad){return rad*180/PI;}



inline int geti(int &_int){return scanf("%d", &_int);}

inline int getii(int &_int, int &_int2){return scanf("%d %d", &_int, &_int2);}

inline int getiii(int &_int, int &_int2, int &_int3){return scanf("%d %d %d", &_int, &_int2, &_int3);}



inline int getl(ll &_ll){return scanf("%lld", &_ll);}

inline int getll(ll &_ll, ll &_ll2){return scanf("%lld %lld", &_ll, &_ll2);}

inline int getlll(ll &_ll, ll &_ll2, ll &_ll3){return scanf("%lld %lld %lld", &_ll, &_ll2, &_ll3);}



inline int getd(double &_double){return scanf("%lf", &_double);}

inline int getdd(double &_double, double &_double2){return scanf("%lf %lf", &_double, &_double2);}



inline int getstr(char *str){return scanf("%s", str);}



//#define isValid(a, b) (a >= 0 && a < b)

//int dr[]  =  {0, -1, -1, -1,  0,  1, 1, 1};

//int dc[]  =  {1,  1,  0, -1, -1, -1, 0, 1};

bool status[MAX];

vector<int>primes;



void sieve()

{

    status[1] = 1;

    primes.pb(2);

    for(int i = 3; i*i < MAX; i++){

        if(!status[i]){

            primes.pb(i);

            //what_is(i*i);

            for(ll j = (ll)i*i; j < MAX; j+=i+i)

                status[j] = 1;

        }

    }

}



int cnt[MAX];



int main(int argc, char* argv[])

{

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    sieve();

    cnt[3]=1;

    for(int i = 4; i < MAX; i++){

        cnt[i] = cnt[i-1];

        if((i%2 ==1 && ((i+1)/2)%2==1 && !status[i] && !status[(i+1)/2]) || i == 2017)

           cnt[i]++;

    }

    int q, l, r;

    cin >> q;

    while(q--){

        cin >> l >> r;

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

    }

    return 0;

}