#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;//(1LL<<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 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 PI (acos(-1))
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 である。

SegmentTree(n, f, M1):= サイズ n の初期化。
	f は2つの区間の要素をマージする二項演算,
	M1 はモノイドの単位元である。
set(k,x):= k 番目の要素に x を代入する。
build():= セグメント木を構築する。
query(a,b):= 区間 [a,b) に対して二項演算した結果を返す。
update(k,x):= k 番目の要素を x に変更する。
operator[k] := k 番目の要素を返す。
*/
template<typename Monoid>
class SegmentTree {
public:
	using F = function<Monoid(Monoid, Monoid)>;

	ll size;
	vector< Monoid > seg;

	const F f;
	const Monoid M1;
 
	SegmentTree(ll n, const F f, const Monoid &M1) : f(f), M1(M1) {
		size = 1;
		while(size < n) size <<= 1;
		seg.assign(2 * size, M1);
	}
	
	void set(ll k, const Monoid &x) {
		seg[k + size] = x;
	}

	void build() {
		for(ll k = size - 1; k > 0; k--) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}
	
	void update(ll k, const Monoid &x) {
		k += size;
		seg[k] = x;
		while(k >>= 1) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	Monoid query(ll a, ll b) {
		Monoid L = M1, R = M1;
		for(a += size, b += size; a < b; a >>= 1, b >>= 1) {
			if(a & 1) L = f(L, seg[a++]);
			if(b & 1) R = f(seg[--b], R);
		}
		return f(L, R);
	}

	Monoid operator[](const ll &k) const {
		return seg[k + size];
	}
};


////

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;

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

	SegmentTree<ll> st(N, [](ll x,ll y){return x+y;}, 0LL);
	//SegmentTree<ll> st(N, gcd, 0LL);

	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: 3072