#include<iostream>
#include<cmath>
#include<cstdio>
int sushu(int m)
{
	int i,flog=0;
	if(m==1)
	return 0;
	else
	{
	for(i=2;i<=sqrt(m);i++)
	{
		if(m%i==0)
		{
			flog=1;
			break;
		}
	}
	if(flog==1)
	return 0;
	else
	return 1;
}
}
using namespace std;
int main()
{
int n,i,sum=0,j;
cin>>n;
int a[n*2];
for(i=0;i<2*n;i++)
{
	cin>>a[i];
}
for(i=0;i<n;i++)
{
	for(j=a[i*2];j<=a[i*2+1];j++)
	{
		if(sushu(j))
		sum++;
	}
	cout<<sum<<endl;
	sum=0;
}
}