#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep0(N) for (int COUNTER = 0; COUNTER < (int)(N); COUNTER++)
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define rep1(i, N) for (int i = 0; i < (int)(N); i++)
#define rep2(i, START, GOAL) for (int i = (int)(START); i < (int)(GOAL); i++)
#define rep3(i, START, GOAL) for (int i = (int)(START); i > (int)(GOAL); i--)
#define ALL(CONTAINER) CONTAINER.begin(), CONTAINER.end()
#define rALL(CONTAINER) CONTAINER.rbegin(), CONTAINER.rend()
#define from1(CONTAINER) CONTAINER.begin() + 1, CONTAINER.end()
#define rfrom1(CONTAINER) CONTAINER.rbegin(), CONTAINER.rend() - 1
#define output(X) cout << X << "\n"
#define dberr(X) cerr << X << "\n"
#define db(X) cerr << #X << ":" << (X) << " "
#define dbl(X) cerr << #X << ":" << (X) << "\n"
#define db2(X, Y) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << " "
#define db2l(X, Y) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << "\n"
#define dbl2(X, Y) cerr << #X << ":" << (X) << "\n" << #Y << ":" << (Y) << "\n"
#define db3(X, Y, Z) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << " " << #Z << ":" << (Z) << " "
#define db3l(X, Y, Z) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << ", " << #Z << ":" << (Z) << "\n"
#define dbl3(X, Y, Z) cerr << #X << ":" << (X) << "\n" << #Y << ":" << (Y) << "\n" << #Z << ":" << (Z) << "\n"
#define dbp(PAIR) cerr << #PAIR << ":(" << PAIR.first << ", " << PAIR.second << ") "
#define dbpl(PAIR) cerr << #PAIR << ":(" << PAIR.first << ", " << PAIR.second << ")\n"
#define dbt3(TUPLE3) cerr << #TUPLE3 << ":(" << get<0>(TUPLE3) << ", " << get<1>(TUPLE3) << ", " << get<2>(TUPLE3) << ") "
#define dbt3l(TUPLE3) cerr << #TUPLE3 << ":(" << get<0>(TUPLE3) << ", " << get<1>(TUPLE3) << ", " << get<2>(TUPLE3) << ")\n"
#define dbt4(TUPLE4) cerr << #TUPLE4 << ":(" << get<0>(TUPLE4) << ", " << get<1>(TUPLE4) << ", " << get<2>(TUPLE4) << ", " << get<3>(TUPLE4) << ") "
#define dbt4l(TUPLE4) cerr << #TUPLE4 << ":(" << get<0>(TUPLE4) << ", " << get<1>(TUPLE4) << ", " << get<2>(TUPLE4) << ", " << get<3>(TUPLE4) << ")\n"
#define dbv(VEC) cerr << #VEC << ":{ "; for (auto ELEM : VEC) cerr << ELEM << ", "; cerr << "}\n"
#define dbvp(VP) cerr << #VP << ":{ "; for (auto PAIR : VP) cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; cerr << "}\n"
#define dbvv(VV) cerr << #VV << ":{\n"; for (auto VEC : VV) { cerr << "{ "; for (auto ELEM : VEC) cerr << ELEM << ", "; cerr << "},\n"; } cerr << "}\n"
#define dbvvp(VVP) cerr << #VVP <<":{\n"; for (auto VP : VVP) { cerr << "{ "; for (auto PAIR : VP) { cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; } cerr << "},\n"; } cerr << "}\n";
#define dbm(MAP) cerr << #MAP << ":{ "; for (auto PAIR : MAP) cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; cerr << "}\n"
#define YN(f) cout << (f ? "YES" : "NO") << "\n"
#define Yn(f) cout << (f ? "Yes" : "No") << "\n"
#define yn(f) cout << (f ? "yes" : "no") << "\n"
using ll = long long;
using vi = vector<int>; using vl = vector<ll>; using vd = vector<double>; using vs = vector<string>; using vb = vector<bool>;
using vvi = vector<vi>; using vvl = vector<vl>; using vvd = vector<vd>; using vvb = vector<vb>;
using pii = pair<int, int>; using pil = pair<int, ll> ; using pli = pair<ll, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>;
using vpii = vector<pii>; using vpll = vector<pll>; using vpdd = vector<pdd>;
using ti3 = tuple<int, int, int>; using tl3 = tuple<ll, ll, ll>; using td3 = tuple<double, double, double>;
using ti4 = tuple<int, int, int, int>; using tl4 = tuple<ll, ll, ll, ll>; using td4 = tuple<double, double, double, double>;
using mii = map<int, int>; using mil = map<int, ll>; using mli = map<ll, int>; using mll = map<ll, ll>;
using si = set<int>; using sl = set<ll>;
// db
pii divs(int N, int prm) { // Nをprmで割れるだけ割った商と割った回数
	assert(N % prm == 0);
	int deg = 0;
	while (N % prm == 0) {
		N /= prm;
		deg++;
	}
	return pii(N, deg);
}
/*
// (1.1) 2以上の全ての整数で割る方法
mii PF(int N) {
	assert(N > 0);
	mii res;
	int prm = 2, deg;
	while (prm * prm <= N) {
		if (N % prm == 0) {
			tie(N, deg) = divs(N, prm);
			res[prm] = deg;
		}
		prm++;
	}
	if (N > 1) res[N] = 1;
	return res;
}
*/
// (1.2) 2及び3以上の奇数で割る方法(少し速い)
mii PF(int N) {
	assert(N > 0);
	mii res;
	int prm = 2, deg;
	if (N % prm == 0) {
		tie(N, deg) = divs(N, prm);
		res[prm] = deg;	
	}	
	prm = 3;
	while (prm * prm <= N) {
		if (N % prm == 0) {
			tie(N, deg) = divs(N, prm);
			res[prm] = deg;
		}
		prm += 2;
	}
	if (N > 1) res[N] = 1;
	return res;
}

// (2) 素数判定
bool isprime(int N) {
	assert(N > 0);
	return PF(N).size() == 1 and PF(N).begin()->second == 1;
}

const int MAX = 1e5;
vi dp(MAX + 1); // dp[i + 1]:i以下の2017に似た奇数の個数

void init() {
	for (int i = 3; i < MAX; i += 2) {
		if (isprime(i) and isprime((i + 1) / 2)) dp[i + 1] = dp[i - 1] + 1;
		else dp[i + 1] = dp[i - 1];
	}
}

int main() {
	init();
	// dbv(dp);
	int Q; cin >> Q;
	rep0(Q) {
		int l, r; cin >> l >> r;
		output(dp[r + 1] - dp[l - 1]);
	}	
}

Measured memory_bytes: 1024