#include<bits/stdc++.h>
using namespace std;
const int ms = 1e5+9;
bitset<ms> bs;
int vet[ms];

void sieve(){
	bs[0] = bs[1] = 1;
	for(int i = 2;i<ms;i++){
		if(!bs[i])
			for(int j = i+i;j<ms;j+=i)
				bs[j] = 1;
	}
	
}

int main(){
	int q,a,b;
	
	sieve();
	
	for(int i = 1;i<ms;i++){
		if(!bs[i] and !bs[(i+1)/2])
			vet[i]++;
	}
	for(int i = 1;i<ms;i++)
		vet[i] += vet[i-1];

	cin >> q;
	while(q--){
		cin >> a >> b;
		cout<<(vet[b]-vet[a-1])<<endl;
		
	
	}
}