/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <utility>
#include <vector>
#include <random>
#include <chrono>
#include <cassert>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <complex>
#include <stack>
#include <array>
#include <unordered_set>
#include <climits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pii;

typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;

template<class T> bool ckmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>


template <typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template <typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template <class X, class Y>
std::ostream & operator << (std::ostream & os, std::pair <X, Y> const& p) {
    return os << p.first << " " << p.second;
}

template <class Ch, class Tr, class Container>
std::basic_ostream <Ch, Tr> & operator << (std::basic_ostream <Ch, Tr>& os, Container const& x) {
    bool first = true;
    for(auto& y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}



#include <cstddef>

bool isPrime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return n >= 2;
}

bool isPrime(int64_t n) {
    for (int64_t i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return n >= 2;
}

std::vector<bool> primeMap(std::size_t maxN) {
    std::vector<bool> prime(maxN + 1, true);

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

    for (std::size_t i = 2; i * i <= maxN; ++i) {
        if (prime[i]) {
            if (i * 1ULL * i <= maxN) {
                for (std::size_t j = i * i; j <= maxN; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
    return prime;
}

std::vector<int> allPrimes(int maxN) {
    std::vector<int> result;
    result.reserve(maxN);
    std::vector<bool> map = primeMap(maxN);
    for (int i = 0; i <= maxN; i++) {
        if (map[i]) {
            result.push_back(i);
        }
    }
    return result;
}

int nextPrime(int n) {
    while (!isPrime(n)) {
        ++n;
    }
    return n;
}


using namespace std;

class D2017LikeNumber {
    static const int N = 200'000;

    vi counter;

public:
    void solve(std::istream& in, std::ostream& out) {
        int q;
        in >> q;
        FOR(i, 0, q) {
            int l, r;
            in >> l >> r;
            int res = counter[r] - counter[l - 1];
            out << res << '\n';
        }
    }

    void setup() {
        counter.resize(2 * N + 1);
        vector<bool> sieve = primeMap(2 * N);
        FOR(i, 1, 2 * N + 1) {
            counter[i] = counter[i - 1];
            if (i % 2 and sieve[i] and sieve[(i + 1) / 2]) {
                counter[i]++;
            }
        }
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
	D2017LikeNumber solver;
    solver.setup();
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 4688