#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#ifdef _MSC_VER
int getchar_unlocked() { return getchar(); }
#endif
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << endl;
#define qp(f) [](auto i){return f;}
using LL=long long;
using VI=vector<int>;
using VL=vector<LL>;
using VS=vector<string>;
using VVI=vector<vector<int>>;
using PII=pair<int, int>;
const int inf = (int)1e9;
const LL MOD = 1000000007;
const double pi = acos(-1.0);
const string Snum = "0123456789";
const int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
template<class T>T Sort(T& a) { sort(a.begin(), a.end()); return a; }
template<class T>T ReSort(T& a) { sort(a.rbegin(), a.rend()); return a; }
template<class T>T Reverse(T& a) { reverse(a.begin(), a.end()); return a; }
template<class T>void Unique(T& a) { a.erase(unique(a.begin(), a.end()), a.end()); }
template<class T>auto Max(T a) { return *max_element(a.begin(), a.end()); }
template<class T>auto Min(T a) { return *min_element(a.begin(), a.end()); }
template<class T, class U>int Count(T a, U c) { return count(a.begin(), a.end(), c); }
template<class T, class U>U Sum(T a, U init = 0) { return accumulate(a.begin(), a.end(), init); }
template<class T>T Age(T a, T b) { return (a + b - 1) / b; }
template<class T>T gcd(T n, T m) { return m == 0 ? n : gcd(m, n % m); }
template<class T>T lcm(T n, T m) { return n / gcd(n, m) * m; }

/* INPUT */
struct inputter_Str {
	vector<string> inputbuffer;
	string operator [](int n) {
		while (inputbuffer.size() <= n) {
			string s; char c = getchar_unlocked();
			while (c != '\0' && c != '\n' && c != '\t' && c != ' ') {
				s.push_back(c); c = getchar_unlocked();
			}
			inputbuffer.push_back(s);
		}
		return inputbuffer[n];
	}
	operator string() {
		string s; char c = getchar_unlocked();
		while (c != '\0' && c != '\n' && c != '\t' && c != ' ') {
			s.push_back(c); c = getchar_unlocked();
		}
		inputbuffer.push_back(s);
		return s;
	}
}in;
struct inputter_Int {
	int operator [](int n) { return stoi(in[n]); }
	operator int() { return stoi(string(in)); }
}ini;
struct inputter_LL {
	LL operator [](int n) { return stoll(in[n]); }
	operator LL() { return stoll(string(in)); }
}inl;
struct inputter_Double {
	double operator [](int n) { return stod(in[n]); }
	operator double() { return stold(string(in)); }
}ind;
vector<int> invi(int n, int m) { vector<int> v(m); for (int i = 0; i < m; ++i)v[i] = ini[n + i]; return v; }
vector<LL> invl(int n, int m) { vector<LL> v(m); for (int i = 0; i < m; ++i)v[i] = inl[n + i]; return v; }
vector<string> invs(int n, int m) { vector<string> v(m); for (int i = 0; i < m; ++i)v[i] = in[n + i]; return v; }
int Suminvi(int n, int m) { return Sum(invi(n, m), 0); }LL Suminvl(int n, int m) { return Sum(invl(n, m), 0LL); }
int Maxinvi(int n, int m) { return Max(invi(n, m)); }   LL Maxinvl(int n, int m) { return Max(invl(n, m)); }
int Mininvi(int n, int m) { return Min(invi(n, m)); }   LL Mininvl(int n, int m) { return Min(invl(n, m)); }
struct inputter_Int_Fast {
	int get() {
		int num = 0; bool neg = false; char c = getchar_unlocked();
		if (c == '-') { neg = true; c = getchar_unlocked(); }
		while ('0' <= c && c <= '9') { num = num * 10 + (c - '0'); c = getchar_unlocked(); }
		return neg ? -num : num;
	}
	operator int() { return get(); }
}inif;
struct inputter_LL_Fast {
	LL get() {
		LL num = 0; bool neg = false; char c = getchar_unlocked();
		if (c == '-') { neg = true; c = getchar_unlocked(); }
		while ('0' <= c && c <= '9') { num = num * 10LL + LL(c - '0'); c = getchar_unlocked(); }
		return neg ? -num : num;
	}
	operator LL() { return get(); }
}inlf;
vector<int> invif(int n) {
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		int num = 0; bool neg = false; char c = getchar_unlocked();
		if (c == '-') { neg = true; c = getchar_unlocked(); }
		while ('0' <= c && c <= '9') { num = num * 10 + (c - '0'); c = getchar_unlocked(); }
		v[i] = neg ? -num : num;
	}
	return v;
}
vector<LL> invlf(int n) {
	vector<LL> v(n);
	for (int i = 0; i < n; ++i) {
		LL num = 0; bool neg = false; char c = getchar_unlocked();
		if (c == '-') { neg = true; c = getchar_unlocked(); }
		while ('0' <= c && c <= '9') { num = num * 10LL + LL(c - '0'); c = getchar_unlocked(); }
		v[i] = neg ? -num : num;
	}
	return v;
}


/* OUTPUT */
ostream& operator << (ostream& ostr, inputter_Str i) { ostr << string(i); return ostr; }
struct boolswitch { string t, f; boolswitch(string tr, string fa) :t(tr), f(fa) {} }yes("yes", "no"), Yes("Yes", "No"), YES("YES", "NO"), Yay("Yay!", ":(");
struct divizer { string s; divizer(string s_) :s(s_) {} }spc(" "), nosp(""), comma(",");
struct outputter {
	bool flag = false; boolswitch bs; divizer di;
	outputter(bool f, boolswitch b, divizer d) :flag(f), bs(b), di(d) {}
	template<class T>outputter operator ,(T o) {
		if (flag)cout << di.s; cout << o;
		outputter t(true, bs, di); return t;
	}
	outputter operator ,(double o) {
		if (flag)cout << di.s; printf("%.20f", o);
		outputter t(true, bs, di); return t;
	}
	outputter operator ,(bool o) {
		if (flag)cout << di.s; cout << (o ? bs.t : bs.f);
		outputter t(true, bs, di); return t;
	}
	template<class T> outputter operator ,(vector<T> o) {
		if (flag)cout << di.s;
		for (int i = 0; i < (int)o.size(); ++i)cout << o[i] << (i == (int)o.size() - 1 ? "" : di.s);
		outputter t(true, bs, di); return t;
	}
	template<class T, class U> outputter operator ,(pair<T, U> o) {
		if (flag)cout << di.s; cout << "[" << o.first, ", " << o.second << "]";
		outputter t(true, bs, di); return t;
	}
	outputter operator ,(outputter o) { cout << '\n'; return o; }
	outputter operator ,(boolswitch b) { outputter t(flag, b, di); return t; }
	outputter operator ,(divizer d) { outputter t(flag, bs, d); return t; }
}out(false, Yes, spc);


//エラトステネスの篩
int Num = 100099;
vector<bool> p(Num, true);
void Eratosthenes() {
	p[0] = false;
	p[1] = false;
	for (int i = 0; i < Num; ++i)if (p[i])
		for (int j = i * 2; j < Num; j += i)p[j] = false;
}

vector<bool> num(Num);
vector<int> rui(Num);

int main() {
	Eratosthenes();
	for (int i = 1; i <= 100009; i += 2) {
		if (p[i] && p[(i + 1) / 2])num[i] = true;
	}
	rui[0] = 0;
	FOR(i, 1, 100009) {
		rui[i] = rui[i - 1] + num[i];
	}

	int q = inif;
	rep(i, q) {
		int l = inif, r = inif;
		out, rui[r] - rui[l - 1], out;
	}
}

Measured memory_bytes: 1024