#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int q,i,j,x,y;
	cin>>q;
	int a[100005],b[100005],c[100005];
	for(i=2;i<=100000;i++)
		a[i]=1;
	for(i=2;i<=int(sqrt(100000));i++)
		if(a[i]==1)
		{
			for(j=i+i;j<=100000;j+=i)
				a[j]=0;
		}
	for(i=3;i<=100000;i++)
	{
		if(a[i]==1 && a[(i+1)/2]==1)
			b[i]=1;
		else
			b[i]=0;
	}
	c[1]=0;
	c[2]=0;
	for(i=3;i<=100000;i++)
		c[i]=c[i-1]+b[i];
	for(i=1;i<=q;i++)
	{
		cin>>x>>y;
		cout<<c[y]-c[x-1]<<endl;
	}
	return 0;
}