10533

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

bool prime[1000001];
bool firstPrime[1000001];
int primeCount[1000001];

bool checkdigit(int a)
{
	int sum;
	if(a<10)
	return 1;
	else
	{
		sum=0;
		while(a)
		{
			sum+=a%10;
			a/=10;
		}
		if(firstPrime[sum]==0)
		return 1;
		else
		return 0;
	}
	return 0;
}
int main()
{
	int cnt=0;
	prime[0]=1;
	prime[1]=1;
	firstPrime[0]=1;
	firstPrime[1]=1;
	primeCount[0]=cnt;
	primeCount[1]=cnt;
	for(int i=2;i<1000001;i++)
	{
		if(prime[i]==0)
		{
			if(!checkdigit(i))
				prime[i]=1;
			else
			{
				cnt+=1;
			}
			for(int j=i+i;j<1000001;j+=i)
			{
				prime[j]=1;
				firstPrime[j]=1;
			}
		}
		primeCount[i]=cnt;
	}
	int t,a,b,add;
	scanf("%d",&t);
	while(t--)
	{
		add=0;
		scanf("%d%d",&a,&b);
		if(firstPrime[a]==0 && checkdigit(a))
		add=1;
		printf("%d\n",primeCount[b]-primeCount[a]+add);
	}
	return 0;
}