#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define gridif(a,x,b) if((a)<=(x)&&(x)<(b))

using namespace std;
typedef pair<int,int> P;
const int mod=1000000007;

int digitsum(int n,int b){
	if(b<2) return -1;
	if(n<b) return n;
	return digitsum(n/b,b)+n%b;
}
int mpow(int a,int x){
	int ans=1;
	while(x>0){
		if(x%2==1) (ans*=a)%=mod;
		(a*=a)%=mod;
		x>>=1;
	}
	return ans;
}
int m_inv(int n){return mpow(n,mod-2);}
vector<int> split(string s,int a){
	if(a<0||a>s.length()) return {-1,-1};
	string l="0",r="0";
	if(a!=0) l=s.substr(0,a);
	if(a!=s.length()) r=s.substr(a);
	return{stoll(l),stoll(r)};
}
string xal_number(int n,int x){
	if(x>36) return "out of use";
	if(n==0) return "";
	string s;
	int i=n%x;
	char a = i + ( i >= 10 ? 'A'-10 : '0' );
	s=xal_number(n/x,x)+a;
	return s;
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
class Factorial{
private:
	vector<int> fac;
public:
	Factorial(int N){
		fac.push_back(1);
		rep(i,N) fac.push_back(fac[i]*(i+1)%mod);
	}
	int fact(int a){return fac[a];}
	int ifac(int a){return m_inv(fac[a]);}
	int cmb(int n,int r){
		if(n<r) return 0;
		if(r==0||r==n) return 1;
		return fac[n]*ifac(r)%mod*ifac(n-r)%mod;
	}
};
struct UnionFind {
    vector<int> par; // 親ノード
    UnionFind(int n = 1) { init(n);}
    void init(int n = 1) {
        par.resize(n);
        rep(i,n) par[i] = -1;
    }
    int root(int x) {
        if (par[x] <0) return x;
        else return par[x] = root(par[x]);      
    }
    int size(int x){ return -par[root(x)];}
    bool issame(int x, int y) {return root(x)==root(y);}
    bool connect(int x,int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
	}
};
struct edge{int from;int to;int cost;};
template<int N> class Graph{
private:
	int inf=1LL<<40;
	vector<edge> e;
	vector<vector<int>> dist;
public:
	Graph(){
		dist.resize(N,vector<int>(N));
		rep(i,N) rep(j,N) dist[i][j]=(i==j)?0:inf;
	}
	Graph(const Graph &cp){dist=cp.dist;e=cp.e;}
	void push(int a,int b,int c){
		e.emplace_back();
		e.back().from=a;e.back().to=b;e.back().cost=c;
	}
	void reverse(){
		rep(i,e.size()) swap(e[i].from,e[i].to);
	}
	int distance(int a,int b){return dist[a][b];}
	void load(int M){
		e.resize(M);
		rep(i,M){
			int a,b;
			cin>>a>>b;a--;b--;
			e[i].from=a;e[i].to=b;e[i].cost=1;
		}
	}
	void wload(int M){
		e.resize(M);
		rep(i,M){
			int a,b,c;
			cin>>a>>b>>c;a--;b--;
			e[i].from=a;e[i].to=b;e[i].cost=c;
		}
	}
	void undirect(){
		int m=e.size();
		e.resize(2*m);
		rep(i,m){
			e[i+m].from=e[i].to;
			e[i+m].to=e[i].from;
			e[i+m].cost=e[i].cost;
		}
	}
	void out(){
		rep(i,e.size()) cout<<e[i].from+1<<" "<<e[i].to+1<<endl;
	}
	void bfs(int s){
		vector<vector<P>> graph(N);
		rep(i,e.size()) graph[e[i].from].push_back(P(e[i].cost,e[i].to));
		queue<int> que;
		que.push(s);
		while(!que.empty()){
			int u=que.front();que.pop();
			rep(i,graph[u].size()){
				int v=graph[u][i].second;
				if(dist[s][v]!=inf) continue;
				que.push(v);dist[s][v]=dist[s][u]+graph[u][i].first;
			}
		}
	}
	void dijkstra(int s){
		vector<vector<P>> graph(N);
		rep(i,e.size()) graph[e[i].from].push_back(P(e[i].cost,e[i].to));
		priority_queue<P,vector<P>,greater<>> que;
		que.push(P(s,0));
		while(!que.empty()){
			P p=que.top();que.pop();
			int u=p.first;
			if(dist[s][u]<p.second) continue;
			rep(i,graph[u].size()){
				int v=graph[u][i].second;
				int alt=dist[s][u]+graph[u][i].first;
				if(dist[s][v]>alt){
					dist[s][v]=alt;
					que.push(P(v,alt));
				}
			}
		}
	}
	void shortest_path(){
		rep(i,e.size()) dist[e[i].from][e[i].to]=e[i].cost;
		rep(k,N) rep(i,N) rep(j,N){
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
		}
	}
	void bellman(int s){
		rep(i,N-1) rep(j,e.size()){
			dist[s][e[j].to]=min(dist[s][e[j].from]+e[j].cost,dist[s][e[j].to]);
		}
	}
	bool nloop(int s,int t){
		bellman(s);
		vector<bool> negative(N,false);
		rep(i,N) rep(j,e.size()){
			if(dist[s][e[j].to]>dist[s][e[j].from]+e[j].cost){
				dist[s][e[j].to]=dist[s][e[j].from]+e[j].cost;
				negative[e[j].to]=true;
			}
			if(negative[e[j].from]) negative[e[j].to]=true;
		}
		if(negative[t]) return true;
		else return false;
	}
	int prim(){
		vector<vector<P>> graph(N);
		rep(i,e.size()) graph[e[i].from].push_back(P(e[i].cost,e[i].to));
		vector<bool> used(N,false);
		priority_queue<P,vector<P>,greater<>> que;
		que.push(P(0,0));
		int ret=0;
		while(!que.empty()){
			P p=que.top();que.pop();
			int u=p.second;
			if(used[u]) continue;
			used[u]=true;
			ret+=p.first;
			rep(i,graph[u].size()) que.push(P(graph[u][i].first,graph[u][i].second));
		}
		return ret;
	}
	Graph<N> kruskal(){
		Graph<N> G;
		sort(All(e),[](const edge &x,const edge &y){return x.cost<y.cost;});
		UnionFind uni(N);
		rep(i,e.size()){
			if(uni.connect(e[i].from,e[i].to)){
				G.push(e[i].from,e[i].to,e[i].cost);
			}
		}
		return G;
	}
};
class Sosu{
 private:
    vector<int> Prime_Number;
 public:
    Sosu(int N){
        set<int> arr;
        rep(i,N-1)  arr.insert(i+2);
        while(int n=*arr.begin()){
            if(n>sqrt(N)) break;
            Prime_Number.push_back(n);
            rep(i,1,N/n+1) arr.erase(n*i);
        }
        itr(it,arr) Prime_Number.push_back(*it);
    }
    int operator[](int i){return Prime_Number[i];}
    int count(){return Prime_Number.size();}
    bool isPrime(int q){return binary_search(All(Prime_Number),q);}
};
signed main(){
	int q;
	cin>>q;
	Sosu p(100001);
	int S[100001];
	rep(i,1,100001){ 
		S[i]=S[i-1];
		if(i&1){ 
			if(p.isPrime(i)&&p.isPrime((i+1)/2)){
				S[i]++;
			}
		}
	}
	rep(i,q){
		int l,r;
		cin>>l>>r;
		cout<<S[r]-S[l-1]<<endl;
	}
}





Measured memory_bytes: 6272