//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <tuple> 
using namespace std;
typedef long long ll;

//input
//------------------------------------------
#define re(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest&...rest) { cin >> first; MACRO_VAR_Scan(rest...); }
#define rv_row(type, n, ...)vector<type> __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int i=0; i<n; ++i){MACRO_VEC_ROW_Scan(i, __VA_ARGS__);}
template<typename T> void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Init(int n, First& first, Rest&...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); }
template<typename T> void MACRO_VEC_ROW_Scan(int p, T& t) { cin >> t[p]; }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Scan(int p, First& first, Rest&...rest) { cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); }
#define rv(type, c, n) vector<type> c(n);for(auto& i:c)cin>>i;
#define rMAT(type, c, n, m) vector<vector<type>> c(n, vector<type>(m));for(auto& r:c)for(auto& i:r)cin>>i;  
void _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
// output
//------------------------------------------
#define pr(x) cout<<x<<endl;
#define prv(v){for(const auto& xxx : v){cout << xxx << " ";}cout << "\n";}
#define sankou(x,a,b) cout<<(x?a:b)<<endl;
#define hihumi(x,a,y,b,c) cout<<(x?a:y?b:c)<<endl;
#define YESNO(x) cout<<(x?"YES":"NO")<<endl;
#define yesno(x) cout<<(x?"Yes":"No")<<endl;
#define ck(x)  cerr << #x << " = " << (x) << endl;
#define ckv(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
//conversion
//------------------------------------------
inline ll toInt(std::string s) { ll v; std::istringstream sin(s);sin >> v;return v; }
template<class T> inline string toString(T x) { ostringstream sout;sout << x;return sout.str(); }
//math
//------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }
template<typename A, typename B>inline void chmin(A &a, B b) { if (a>b)a = b; }
template<typename A, typename B>inline void chmax(A &a, B b) { if (a<b)a = b; }
ll qp(ll a, ll b) { ll ans = 1ll;do { if (b & 1)ans = 1ll * ans*a;a = 1ll * a*a; } while (b >>= 1);return ans; }
ll qpmod(ll a, ll b, ll mo) { ll ans = 1ll;do { if (b & 1)ans = 1ll * ans*a%mo;a = 1ll * a*a%mo; } while (b >>= 1);return ans; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline bool valid(int x, int h) { return 0 <= x && x < h; }
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTST(s,c) (((s).find(c)) != std::string::npos)
#define SORT(c) sort((c).begin(),(c).end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,val) (lower_bound(x.begin(),x.end(),val)-x.begin())
#define POSU(x,val) (upper_bound(x.begin(),x.end(),val)-x.begin())
#define FI first
#define SE second
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMINF(a) memset(a,0x3f,sizeof(a))//1e9<1061109567<INTMAX/2
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define FORll(i,a,b) for(long long i=(a);i<(b);++i)
#define repll(i,n) FORll(i,0,n)
#define rrep(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define rrepll(i,a,b) for(long long i=(b)-1ll;i>=a;i--)
#define fo(x,c) for(auto &x : c)

#define repeat(i,a,b) for(int i=(a);i<=(b);++i)
//typedef
//------------------------------------------
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<pair<int, int>> vpii;
//constant
//------------------------------------------
const double EPS = 1e-8;
const double PI = acos(-1.0);
const int INF = (int)(1e9) + 7;
const ll MOD = (ll)(1e9) + 7;
const ll MOD2 = (ll)(1e18) + 9;
#define ADD(a, b) a = (a + ll(b)) % MOD
#define MUL(a, b) a = (a * ll(b)) % MOD
const ll INF2 = (ll)(1e18);
const ll INTMAX = (0x7FFFFFFFL);
const ll LLMAX = (0x7FFFFFFFFFFFFFFFL);
const int N4 = (int)1e4 + 10;
const int N5 = (int)1e5 + 10;
int dx[8] = { 1, 0, -1, 0 , 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, -1, -1,  1, 1 };
//------------------------------------------


ll ans, cnt, ret, cur, f;

std::vector<int> eratosthenes_sieve(int n) {
    std::vector<int> ps(n + 1);
    std::iota(ps.begin() + 2, ps.end(), 2);
    for (int i = 2; i * i <= n; ++i)
        if (ps[i])
            for (int j = i * i; j <= n; j += i) ps[j] = 0;
    return ps;
}

std::vector<int> make_primes(int n) {
    std::vector<int> ps = eratosthenes_sieve(n);
    ps.erase(std::remove(ps.begin(), ps.end(), 0), ps.end());
    return ps;
}

template <class T>
struct BIT {
    int n;
    std::vector<T> x;
    BIT(int n_ = 0) : n(n_), x(n + 1, 0) {}
    int size() const { return n; }
    T sum(int r) const {
        T S = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
        return S;
    }
    T sum(int l, int r) const { return sum(r) - sum(l); }
    void add(int k, const T &a) {
        for (; k < n; k |= k + 1) x[k] += a;
    }
    void set(int k, const T &a) { add(k, a - sum(k, k + 1)); }
};


void _main() {
    int n = 100010;
    vi v = make_primes(n);
    set<int> prime;
    BIT<int>bt(n);
    fo(x, v)prime.emplace(x);
    fo(x, v)if (EXIST(prime, (x + 1) / 2))bt.add(x, 1);
    re(int, q);
    rep(_, q) {
        re(int, from, to);
        pr(bt.sum(from, to + 1));
    }
}

Measured memory_bytes: 1920