// Original C++ solution (slower):
#include<algorithm>

#include<cmath>

#include<iomanip>

#include<iostream>

#include<map>

#include<numeric>

#include<queue>

#include<set>

#include<sstream>

#include<unordered_map>

#include<unordered_set>

#include<vector>

using uint = unsigned int;

using ll = long long;

enum : int { M = (int)1e9 + 7 };

enum : ll { MLL = (ll)1e18L + 9 };

using namespace std;

#ifdef LOCAL

#include"rprint2.hpp"

#include"debug_deque.hpp"

#define vector DebugDeque

#else

#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }

FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);

#endif



#include<unistd.h>

struct Buffer{

    int idx;

    char buf[1025];

    Buffer(){ init(); }

    void init(){ idx = 0; read(0, buf, 1024); }

    void check(){ if(idx == 1024){ init(); } }

    int next(){

        static char notDigits[256] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, 0,0,0,0,0,0,0,0,0,0,};

        int ret = 0, sign = 1;

        while(check(), notDigits[(int)buf[idx]]){ idx++; }

        if(check(), buf[idx] == '-'){ sign = -1; idx++; }

        while(check(), !notDigits[(int)buf[idx]]){ ret = ret * 10 + buf[idx++] - '0'; }

        return sign * ret;

    }

};



int main(){

    // cin.tie(0);

    // ios::sync_with_stdio(false);

    Buffer buf;

    int lim = 1e5;

    vector<char> prime(lim + 1, true);

    prime[0] = prime[1] = false;

    for(int i = 2; i <= lim; i++){

        if(prime[i]){

            for(int j = i + i; j <= lim; j += i){

                prime[j] = false;

            }

        }

    }

    vector<int> accs(lim + 1);

    for(int i = 1; i <= lim; i++){

        accs[i] = accs[i - 1] + (i & 1 && prime[i] && prime[(i + 1) / 2]);

    }

    // int q; cin >> q;

    int q = buf.next();

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

        // int l, r;

        // cin >> l >> r;

        int l = buf.next(), r = buf.next();

        cout << accs[r] - accs[l - 1] << '\n';

    }

}


// Optimized solution to the same problem (faster):
#include<algorithm>

#include<cmath>

#include<iomanip>

#include<iostream>

#include<map>

#include<numeric>

#include<queue>

#include<set>

#include<sstream>

#include<unordered_map>

#include<unordered_set>

#include<vector>

using uint = unsigned int;

using ll = long long;

enum : int { M = (int)1e9 + 7 };

enum : ll { MLL = (ll)1e18L + 9 };

using namespace std;

#ifdef LOCAL

#include"rprint2.hpp"

#include"debug_deque.hpp"

#define vector DebugDeque

#else

#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }

FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);

#endif



#include<unistd.h>

struct Buffer{

    int idx;

    enum { chunk = 1 << 16 };

    char buf[chunk];

    Buffer(){ init(); }

    void init(){ idx = 0; read(0, buf, chunk); }

    void check(){ if(idx == chunk){ init(); } }

    int next(){

        static char notDigits[256] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, 0,0,0,0,0,0,0,0,0,0,};

        int ret = 0, sign = 1;

        while(check(), notDigits[(int)buf[idx]]){ idx++; }

        if(check(), buf[idx] == '-'){ sign = -1; idx++; }

        while(check(), !notDigits[(int)buf[idx]]){ ret = ret * 10 + buf[idx++] - '0'; }

        return sign * ret;

    }

};



int main(){

    // cin.tie(0);

    // ios::sync_with_stdio(false);

    Buffer buf;

    const int lim = 1e5;

    vector<char> prime(lim + 1, true);

    prime[0] = prime[1] = false;

    for(int i = 2; i <= sqrt(lim); i++){

        if(prime[i]){

            for(int j = i + i; j <= lim; j += i){

                prime[j] = false;

            }

        }

    }

    vector<int> accs(lim + 1);

    for(int i = 1; i <= lim; i++){

        accs[i] = accs[i - 1] + (i & 1 && prime[i] && prime[(i + 1) / 2]);

    }

    // int q; cin >> q;

    int q = buf.next();

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

        // int l, r;

        // cin >> l >> r;

        int l = buf.next(), r = buf.next();

        cout << accs[r] - accs[l - 1] << '\n';

    }

}


// Fastest known solution for this problem: