// Original C++ solution (slower):
/*

　　　  ∧＿∧　やあ

　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。

　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。

　　 |:⊃:|:::::|　　　|──|

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。

￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|

　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない

　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。

￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい

￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。

　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|

　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。

　　.／|＼　／|＼ ／|＼

*/



#include <iostream>

#include <cstdlib>

#include <algorithm>

#include <array>

#include <bitset>

#include <climits>

#include <cmath>

#include <cstdio>

#include <deque>

#include <functional>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <string>

#include <vector>

using namespace std;

#define fst first

#define snd second

#define mp make_pair

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

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

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

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

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

#define SIZE(x) ((int)(x).size())

#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';

#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';

typedef long long lint;

typedef pair<int, int> pint;

typedef pair<lint, lint> plint;

typedef vector<lint> vec;

typedef vector<vector<lint>> matrix;

typedef priority_queue<lint> p_que;

typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;

const lint INF = INT_MAX;

const lint LINF = LLONG_MAX;

const lint MOD = 1000000000 + 7;

const double EPS = 1e-9;

const double PI = acos(-1);

const int di[]{0, -1, 0, 1, -1, -1, 1, 1};

const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};



lint gcd(lint a, lint b) {

    lint r;

    while (b != 0) {

        r = a % b;

        a = b; 

        b = r;

    }

    return a;

}



lint lcm(lint a, lint b) {

    return (a / gcd(a, b)) * b;

}



lint power(lint x, lint n, lint mod = MOD) {

    lint ret = 1;

    while(n > 0) {

        if(n & 1){

            (ret *= x) %= mod;

        }

        (x *= x) %= mod;

        n >>= 1;

    }

    return ret;

}



vector<lint> make_power(int n, lint base){

    lint num = 1;

    vector<lint> ret;

    for (int i=0; i<=n; ++i){

        ret.push_back(num);

        num *= base;

    }

    return ret;

}



pair<vector<bool>, vector<int>> eratosthenes(int n){

    vector<int> res;

    vector<bool> is_prime(n + 1, true);

    for (int p = 2; p <= n; p++) {

        if (!is_prime[p]){

            continue;

        }

        for (int k = p * 2; k <= n; k += p){

            is_prime[k] = false;

        }

        res.push_back(p);

    }

    return make_pair(is_prime, res);

}



int q;

vector<int> l, r;



void input(){

    cin >> q;

    l.resize(q);

    r.resize(q);

    REP(i, q){

        cin >> l[i] >> r[i];

    }

    return;

}



void solve(){

    const int max_r = 100010;

    auto er = eratosthenes(max_r);

    vector<lint> sum(max_r, 0);

    for(int i=3; i<=max_r; i+=2){

        // debugpair(i, er.fst[i]);

        if(er.fst[i] && er.fst[(i + 1) / 2]){

            sum[i]++;

        }

    }

    REP(i, max_r-1){

        sum[i+1] += sum[i];

    }

    REP(i, q){

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

    }

}



int main()

{

    cin.tie(0);

    ios_base::sync_with_stdio(false);

    input();

    solve();

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define fi           first

#define se           second

#define ll           long long

#define pb           push_back

#define mp           make_pair

#define pll          pair<ll,ll>

#define pii          pair<int,int>

#define SZ(x)        ((int)(x).size())

#define READ(x)      freopen(x,"r",stdin)

#define WRITE(x)     freopen(x,"w",stdout)

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

#define isWorking()  cout<<"Wroking"<<endl

#define FOR(i,x,y)   for(int i=x; i<y; i++)

#define SORT(x)      sort(x.begin(),x.end())

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

#define Fast_Input   ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

typedef vector<int> VI;

const ll mod= 1e9+7,INF=1e18,mx= 1e5,mn=100;

int testCase=1,cas=0;



bool flag[mx+5];



void seive() {



    for(int i=2; i<=mx; i++)  flag[i]=1;



    int val=sqrt(mx)+1;

    for(int i=2; i<val; i++)

        if(flag[i])

            for(int j=i; j*i<=mx; j++)

                flag[i*j]=0;

}



vector <int> Like;



int main() {

    seive();



    for(int i=3; i<=mx; i+=2){

        int k= (i+1)/2;

        if(flag[i] && flag[k]){

            Like.push_back(i);

        }

    }



    scanf("%d",&testCase);



    while(testCase--) {

        int l,r;

        scanf("%d %d",&l,&r);

        int a= lower_bound(all(Like),l)-Like.begin();

        int b= lower_bound(all(Like),r)-Like.begin();

        if(Like[b]==r) b++;

        printf("%d\n",b-a);

    }

    return 0;

}


// Fastest known solution for this problem: