// Original C++ solution (slower):


//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 <fstream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <string>

#include <cstring>

#include <ctime>





using namespace std;



//conversion

//------------------------------------------

inline int toInt(string s) { int v; 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; }



//typedef

//------------------------------------------

typedef vector<int> VI;

typedef vector<VI> VVI;

typedef vector<string> VS;

typedef pair<int, int> PII;

typedef long long LL;



//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 EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

#define EXIST(s,e) ((s).find(e)!=(s).end())

#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)

#define SORT(c) sort((c).begin(),(c).end())



//repetition

//------------------------------------------

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define rep(i,n)  FOR(i,0,n)

#define loop(n) FOR(i,0,n)

#define rrep(i,a,b) for(int i=(a);i>=(b);--i)

//constant

//--------------------------------------------

const double EPS = 1e-10;

const double PI = acos(-1.0);

const int INF = (int)1000000007;

const LL MOD = (LL)1000000007;//10^9+7

const LL INF2 = (LL)100000000000000000;//10^18



const int maxN = 100010;

bool primes[maxN];



void hurui() {



	for (int i = 0; i < maxN; i++) {

		primes[i] = true;

	}



	primes[0] = false;

	primes[1] = false;



	for (int i = 2; i < maxN; i++) {



		if (primes[i] == false)continue;



		for (int j =2 ; i*j < maxN; j++) {

			primes[i*j] = false;

		}

	}



}





int range[maxN];



int main() {



	hurui();



	for (int i = 3; i < 101010; i += 2) {

		if (primes[i] && primes[(i + 2) / 2]) {

			range[i]++;

		}

	}



	//0～iまでの2017likenumの数を記録しておいて、

	//区間クエリに対しては0～r から0～l-1を引いて求める。

	for (int i = 3; i < 101010; i++) {

		range[i] += range[i - 1];

	}



	int q; cin >> q;

	

	//0------- l-1 l ----r

	//************ l ----r



	for (int i = 0; i < q; i++) {

		int l, r; cin >> l >> r;



		cout << range[r] - range[l - 1] << endl;

	}



	return 0;

}

// Optimized solution to the same problem (faster):


//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 <fstream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <string>

#include <cstring>

#include <ctime>

#include <climits>

#include <limits>



using namespace std;



//conversion

//------------------------------------------

inline int toInt(string s) { int v; 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; }



//typedef

//------------------------------------------

typedef vector<int> VI;

typedef vector<VI> VVI;

typedef vector<string> VS;

typedef pair<int, int> PII;

typedef long long LL;



//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 EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

#define EXIST(s,e) ((s).find(e)!=(s).end())

#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)

#define SORT(c) sort((c).begin(),(c).end())



#define REP(i,n) for(int i=0;i<(int)n;++i)

#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)



//constant

//--------------------------------------------

const double EPS = 1e-10;

const double PI = acos(-1.0);

const int INF = (int)1000000007;

const LL MOD = (LL)1000000007;//10^9+7

const LL INF2 = (LL)100000000000000000;//10^18



vector< bool > isprimetable(int n) {

	vector< bool > prime(n + 1, true);

	if (n >= 0) prime[0] = false;

	if (n >= 1) prime[1] = false;

	for (int i = 2; i * i <= n; i++) {

		if (!prime[i]) continue;

		for (int j = i + i; j <= n; j += i) {

			prime[j] = false;

		}

	}

	return prime;

}







int main() {



	int q; cin >> q;



	vector<int> imos(100010,0);

	

	auto prime = isprimetable(100010);

	for (int i = 1; i < 100000; i++) {

		if (i % 2 == 0) {

			imos[i] = imos[i - 1];

		}

		else {

			if (prime[i] == true && prime[(i + 1) / 2] == true) {

				imos[i] =imos[i - 1]+1;

			}

			else {

				imos[i] = imos[i - 1];

			}

		}

	}



	for (int i = 0; i < q; i++) {

		int l, r; cin >> l >> r;



		cout << imos[r] - imos[l-1] << endl;

	}





	return 0;

}

// Fastest known solution for this problem: