#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>
//#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,s,n) for(int i=(s);i<(n);++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define REPR(i,s,n) for(int i=(s);i>=(n);--(i))
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
const ll mod = 1e9 + 7;
ll dx[4] = { 1,0,-1,0 };
ll dy[4] = { 0,1,0,-1 };

void printvll(vll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) cout << v[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}
void printvvll(vvll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) {
		rep(j, v[i].size()) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void prints(string s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) cout << s[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}

void printvs(vs s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) {
		rep(j, s[i].size()) {
			cout << s[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void Yes(bool x) {
	if (x) cout << "Yes\n";
	else cout << "No\n";
}

void YES(bool x) {
	if (x) cout << "YES\n";
	else cout << "NO\n";
}

void yes(bool x) {
	if (x) cout << "yes\n";
	else cout << "no\n";
}

ll gcd(ll x, ll y)
{
	ll r;

	if (x == 0 || y == 0)  // 引数チェック
	{
		fprintf(stderr, "引数エラーです。\n");
		return 0;
	}

	// ユーグリッドの互除法
	while ((r = x % y) != 0)  // yで割り切れるまでループ
	{
		x = y;
		y = r;
	}
	return y;
}
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

vector<bool> IsPrime;

void sieve(size_t max) {
	if (max + 1 > IsPrime.size()) {     // resizeで要素数が減らないように
		IsPrime.resize(max + 1, true); // IsPrimeに必要な要素数を確保
	}
	IsPrime[0] = false; // 0は素数ではない
	IsPrime[1] = false; // 1は素数ではない

	for (size_t i = 2; i*i <= max; ++i) // 0からsqrt(max)まで調べる
		if (IsPrime[i]) // iが素数ならば
			for (size_t j = 2; i*j <= max; ++j) // (max以下の)iの倍数は
				IsPrime[i*j] = false;      // 素数ではない
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll  c, d, n, m, k, ans = 0, ret = M;
	bool flag = false;
	string s, t;
	ll h, w;
	cin >> n;
	vll l(n), r(n);
	ret *= -1;
	rep(i, n) {
		cin >> l[i] >> r[i];
		ret = max(ret, r[i]);
	}
	sieve(ret + 1);
	vll cur(ret + 1);
	for (int j = 3; j <=ret; j += 2) {
		if (IsPrime[j] && IsPrime[(j + 1) / 2]) cur[j]++;
	}
	REP(i, 3, ret + 1) cur[i] += cur[i - 1];
	rep(i,n){
		cout << cur[r[i]] - cur[l[i] - 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 3072