#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;

//#define int long long
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=1<<31-1=2147483647
constexpr ll INF = (ll)1e18;//1<<63-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define PI (acos(-1))
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define pb push_back
inline bool isnatural(double a) { return a>=0 && ceil(a)==floor(a); }
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

/*
実装では木を 1-indexed の配列で表現している。ノード k について, 親ノードは k/2, 子ノードは 2k, 2k+1 である。

LazySegmentTree(n, f, g, h, M1, OM0):= サイズ n の初期化。
　ここで f は2つの区間の要素をマージする二項演算, 
　g は要素と作用素をマージする二項演算(第三引数は対応する区間の長さ), 
　h は作用素同士をマージする二項演算, M1 はモノイドの単位元, 
　OM0 は作用素の単位元である。
set(k,x):= k 番目の要素に x を代入する。
build():= セグメント木を構築する。
query(a,b):= 区間 [a,b) に対して二項演算した結果を返す。
update(a, b, x) := 区間 [a,b) に作用素 x を適用する。
operator[k] := k 番目の要素を返す。
*/
template< typename Monoid, typename OperatorMonoid = Monoid >
class LazySegmentTree {
public:
	using F = function< Monoid(Monoid, Monoid) >;
	using G = function< Monoid(Monoid, OperatorMonoid, ll) >;
	using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

	ll size;
	vector< Monoid > data;
	vector< OperatorMonoid > lazy;
	const F f;
	const G g;
	const H h;
	const Monoid M1;
	const OperatorMonoid OM0;

	LazySegmentTree(ll n, const F f, const G g, const H h, const Monoid &M1, const OperatorMonoid OM0)
		 : f(f), g(g), h(h), M1(M1), OM0(OM0) {
		size = 1;
		while(size < n) size <<= 1;
		data.assign(2 * size, M1);
		lazy.assign(2 * size, OM0);
	}

	void set(ll k, const Monoid &x) {
		data[k + size] = x;
	}

	void build() {
		for(ll k = size - 1; k > 0; k--) {
			data[k] = f(data[2 * k + 0], data[2 * k + 1]);
		}
	}
	
	void propagate(ll k, ll len) {
		if(lazy[k] != OM0) {
			if(k < size) {
				lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
				lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
			}
			data[k] = g(data[k], lazy[k], len);
			lazy[k] = OM0;
		}
	}

	Monoid update(ll a, ll b, const OperatorMonoid &x, ll k, ll l, ll r) {
		propagate(k, r - l);
		if(r <= a || b <= l) {
			return data[k];
		} else if(a <= l && r <= b) {
			lazy[k] = h(lazy[k], x);
			propagate(k, r - l);
			return data[k];
		} else {
			return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
				update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
		}
	}

	Monoid update(ll a, ll b, const OperatorMonoid &x) {
		return update(a, b, x, 1, 0, size);
	}

	Monoid query(ll a, ll b, ll k, ll l, ll r) {
		propagate(k, r - l);
		if(r <= a || b <= l) {
			return M1;
		} else if(a <= l && r <= b) {
			return data[k];
		} else {
			return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
				query(a, b, 2 * k + 1, (l + r) >> 1, r));
		}
	}

	Monoid query(ll a, ll b) {
		return query(a, b, 1, 0, size);
	}

	Monoid operator[](const ll &k) {
		return query(k, k + 1);
	}
};

////

inline static void upflag(int *flags,int BITS,int i) {
	flags[i / BITS] |= 1 << (i % BITS);
}

inline static int getflag(int *flags,int BITS,int i) {
	return (flags[i / BITS] >> (i % BITS)) & 1;
}

//iが素数の時v[i]=true, 合成数の時v[i]=false なMAXVAL以下のvectorを返す
vector<bool> eratosthenes(int MAXVAL){
	int BITS = (sizeof(int) * 8);
	int FLAGS_NUM = (MAXVAL / BITS + 1);
	int flags[FLAGS_NUM] = {};
	int i, j, f, s;
	int max = (int)sqrt(MAXVAL) + 1;
	vector<bool> primelist(MAXVAL+1,false);
	primelist[2] = true;
	primelist[3] = true;
	for (i = 5, f = 4; i <= max; i += (f = 6 - f)) {
		if (!getflag(flags,BITS,i)) {
			primelist[i] = true;
			s = MAXVAL / i;
			for (j = s - !(s & 1); j >= i; j -= 2) {
				if (!getflag(flags,BITS,i))
					upflag(flags,BITS,i*j);
			}
		}
	}
	for (; i <= MAXVAL; i += (f = 6 - f)){
		if (!getflag(flags,BITS,i)){
			primelist[i] = true;
		}
	}
	return primelist;
}

vector<bool> primelist;

ll add(ll x,ll y){ return x+y; }

signed main() {
	//ABC84D
	//素数上限
	int N=1e5;

	/*
	LazySegmentTree(n, f, g, h, M1, OM0):= サイズ n の初期化。
	　ここで f は2つの区間の要素をマージする二項演算, 
	　g は要素と作用素をマージする二項演算(第三引数は対応する区間の長さ), 
	　h は作用素同士をマージする二項演算, M1 はモノイドの単位元, 
	　OM0 は作用素の単位元である。
	*/
	auto addlambda=[](ll x,ll y){return x+y;};
	auto addlambda1=[](ll x,ll y,ll l){return x+y;};
	LazySegmentTree<ll> st(N, addlambda, addlambda1, addlambda, 0, 0);

	primelist=eratosthenes(N);
	for(int i=3;i<N;i+=2){
		if(primelist[i] && primelist[(i+1)/2]){
			st.set(i,1);
		}
	}

	st.build();

	int q;
	cin >> q;	
	vector<int> answerlist(q,0);
	rep(i,q){
		int x,y;
		cin >> x >> y;
		y++;
		ll answer=st.query(x,y);
		answerlist[i]=answer;
	}

	rep(i,q)p(answerlist[i]);
	return 0;
}




Measured memory_bytes: 5120