#include <bits/stdc++.h>
using namespace std;
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using ll = long long;
constexpr i64 INF = 1010000000000000017LL;
constexpr i64 MOD = 1000000007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) xmax = x; return true;
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) xmin = x; return true;
    return false;
}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH) cout << unitbuf;
    }
} PROCON_INIT;

template <typename TYPE, TYPE Mod>
struct Combination_template
{
    size_t size;
    std::vector<TYPE> fc, inv_fc;
    Combination_template(int N)
    :size(N), fc(size), inv_fc(size)
    {
        fc[0] = 1;
        for (int i = 1; i <= size; ++i) { fc[i] = fc[i - 1] * i % Mod; }
        inv_fc[size] = inv(fc[size]);
        for (int i = size - 1; i >= 0; --i) { inv_fc[i] = inv_fc[i + 1] * (i+1) % Mod; }
    }
    TYPE fact(TYPE n) const { return fc[n]; }
    TYPE inv_fact(TYPE n) const { return inv_fc[n]; }
    TYPE inv(TYPE n) const { return power(n, Mod - 2); }
    TYPE power(TYPE n, TYPE pow) const {
        TYPE res = 1;
        TYPE exp = n;
        for (; pow; pow /= 2) {
            if (pow & 1) res = res * exp % Mod;
            exp = exp * exp % Mod;
        }
        return res;
    }
    TYPE perm(TYPE n, TYPE r) const {
        if (r < 0 || n < r) return 0;
        return fc[n] * inv_fc[n-r] % Mod;
    }
    TYPE binom(TYPE n, TYPE r) const {
        if (n < 0 || r < 0 || n < r) return 0;
        return fc[n] * inv_fc[r] % Mod * inv_fc[n-r] % Mod;
    }
    TYPE homo(TYPE n, TYPE r) const {
        if (n < 0 || r < 0) return 0;
        return r == 0 ? 1 : binom(n + r - 1, r);
    }
};
using Combination = Combination_template<long long, MOD>;

template <typename TYPE>
struct GCD_template
{
    static
    TYPE gcd(TYPE a, TYPE b) {
        if (b == 0) return a;
        else return gcd(b, a % b);
    }
    static
    TYPE extgcd(TYPE a, TYPE b, TYPE& x, TYPE& y) {
        if (b == 0) {
            x = 1; y = 0; return a;
        } else {
            TYPE d = extgcd(b, a % b, y, x);
            y -= a / b * x;
            return d;
        }
    }
    static
    TYPE lcm(TYPE x, TYPE y) {
        return x / gcd(x, y) * y;
    }
};
using GCD = GCD_template<long long>;

template <typename TYPE>
struct Prime_template
{
    TYPE N;
    bool isPrime;
    std::vector<TYPE> factor;
    std::map<TYPE, TYPE> factorized;
    Prime_template(TYPE n)
    :N(n), isPrime(false)
    {
        factor.push_back(1);
        if (N>1) factor.push_back(N);
        for (TYPE i = 2; i*i <= N; ++i) {
            TYPE ex = 0;
            if (N % i == 0) {
                factor.push_back(i);
                TYPE other = N / i;
                if (other != i) factor.push_back(other);
            }
        }
        std::sort(factor.begin(), factor.end());
        isPrime = factor.size() == 2U;
    
        for (TYPE i = 2; i*i <= n; ++i) {
            TYPE ex = 0;
            if (n % i == 0) {
                while (n % i == 0) {
                    ++ex;
                    n /= i;
                }
                factorized.insert(std::make_pair(i, ex));
            }
        }
        if (n != 1) factorized.insert(std::make_pair(n, 1));
    }
};
using Prime = Prime_template<long long>;

template<typename N, typename U>
N calc_digit(N n, U& num) {
    N sum = 0;
    num = 0;
    while(n > 0) {
        ++num;
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

void solve() {
    ll max = 100010;
    vector<ll> prime_list(max, 1);
    prime_list[0] = 0;
    prime_list[1] = 0;
    for (ll i = 2; i < max; ++i) {
        if (!prime_list[i]) continue;
        for (ll j = i*2; j < max; j+=i) prime_list[j]=0;
    }

    vector<ll> like2017(max, 0);
    for (ll i = 0; i < max; ++i) {
        if (i % 2 == 0) continue;
        if (prime_list[i] && prime_list[(i+1)/2]) like2017[i] = 1;
    }

    vector<ll> sum(max+1, 0);
    for (ll i = 0; i < max; ++i) sum[i+1] = sum[i] + like2017[i];

    ll q; cin >> q;
    vector<ll> ans(q);
    for (ll iq = 0; iq < q; ++iq) {
        ll l, r; cin >> l >> r;
        ++r;
        ans[iq] = sum[r] - sum[l];
    }
    for (auto iq : ans) {
        cout << iq << endl;
    }
}

signed main() {
    solve();
    return 0;
}

Measured memory_bytes: 3840