#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 ll MODN = 1000000007;
const ll MODN2 = 998244353;

template<typename T>
class Imos{
    vector<T> v;
    int size;
public:
    Imos(){}
    Imos(int n, T t){
        size = n;
        //前後に番兵のようなものを置く
        for(int i = 0; i < n + 2; i++) v.push_back(t);
    }

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

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

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

    T at(int i){
        assert(0 <= i && i < size);
        return v[i + 1];
    }

    T rangeSum(int l, int r){
        assert(0 <= l && l < r && r <= size);
        return v[r] - v[l];
    }
};

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;
    }
};

int main(){

    int q;
    cin >> q;

    Imos<int> imos(100001, 0);
    Prime prime(100001);

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

    imos.integral();
    imos.integral();

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

    return 0;
}


Measured memory_bytes: 4296