#include <bits/stdc++.h>

#define rep(X, N) for (ll X = 0LL; X < (N); X++)
#define ALL(V) (V).begin(), (V).end()
#define endl "\n"

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

const double PI = 3.1415926535897932384626;
const double EPS = 1e-10;
const ll MODN = 1000000007;
const ll MODN2 = 998244353;

class Prime{
    vector<int> firstFactor;
    vector<int> prime;
    int _n;
public:
    Prime(){}
    Prime(int n){
        _n = n;
        for(int i = 0; i <= n; i++){
            firstFactor.push_back(i);
        }

        for(long long i = 2; i <= n; i++){
            if(i == firstFactor[i]){
                prime.push_back(i);

                for(long long j = i * i; j <= n; j = j + i){
                    firstFactor[j] = min<long long>(i, firstFactor[j]);
                }
            }
        }
    }

    int size(){
        return prime.size();
    }

    int at(int n){
        assert(size() < n);
        return prime[n];
    }

    bool isPrime(int n){
        assert(0 <= n && n <= _n);
        return 2 <= n && n == firstFactor[n];
    }

    vector<pair<long long, int>> factorize(long long n){
        ll maxp = prime[size() - 1];
        assert(n <= maxp * maxp);

        vector<int> count(maxp + 1);
        long long bigger = 0;

        while(n != 1){
            if(n <= maxp){
                int ff = firstFactor[n];
                count[ff]++;
                n /= ff;
            }else{
                bool exist = false;
                for(int i = 0; i < size(); i++){
                    if(n % prime[i] == 0){
                        exist = true;
                        count[prime[i]]++;
                        break;
                    }
                }
                if(!exist){
                    bigger = n;
                    break;
                }
            }
        }

        vector<pair<long long, int>> result;

        for(int i = 2; i <= maxp; i++){
            if(count[i] > 0){
                result.push_back(make_pair(i, count[i]));
            }
        }

        if(bigger != 0){
            result.push_back(make_pair(bigger, 1));
        }

        return result;
    }
};

template<typename T>
class Imos{
    vector<T> v;
    int size;
    bool builded;
public:
    Imos(){}
    Imos(int n, T t){
        size = n;
        for(int i = 0; i <= n; i++) v.push_back(t);
        builded = false;
    }

    void add(int l, int r, T t){
        assert(!builded && 0 <= l && l < r && r <= size);
        v[l] += t;
        v[r] -= t;
    }

    void build(){
        for(int i = 1; i <= size; i++){
            v[i] += v[i - 1];
        }
        builded = true;
    }

    T get(int l, int r){
        assert(builded && 0 <= l && l < r && r <= size);
        return (l == 0 ? v[r - 1] : v[r - 1] - v[l - 1]);
    }
};

int main(){

    int q;
    cin >> q;

    Imos<int> imos(100001, 0);
    cerr << "check" << endl;
    Prime prime(100001);

    cerr << "check" << endl;

    for(int i = 3; i <= 100000; i++){
        if(prime.isPrime(i) && prime.isPrime((i + 1) / 2)){
            //cerr << i << endl;
            imos.add(i, i + 1, 1);
        }
    }

    imos.build();
    imos.build();

    cerr << "builded" << endl;

    rep(i, q){
        int l, r;
        cin >> l >> r;
        cout << imos.get(l, r + 1) << endl;
    }

    return 0;
}


Measured memory_bytes: 4300