#include<bits/stdc++.h>
using namespace std;
bool isPrime[100000005]={false};
void Eratosthenes()
{
	for(int i=2;i<=100000000;i++)
		if(!isPrime[i])
			for(int j=i*2;j<=100000000;j+=i)
				isPrime[j]=true;
} 
int main()
{
	Eratosthenes();
	int T;
	cin>>T;
	for(int i=1;i<=T;i++)
	{
		int a,b,ans=0;
		cin>>a>>b;
		for(int j=a;j<=b;j++)
			if(isPrime[j]==false && (isPrime[j*j+1]==false || isPrime[j*j+2]==false))
				ans++;
		cout<<ans<<"\n";
	}
	return 0;
}

Runtime Error.SIGSEGV