#include <bits/stdc++.h>
using namespace std;
#define N 10000020
#define B 200000001
bitset<B>v;
int cnt;
int q[N];
void oula()
{
	v[1]=1;
	for(int i=2;i<=100000001;i++)
	{
		if(v[i]==0)
		{
			q[++cnt]=i;//i是素数,记录
		}
		for(int j=1;j<=cnt&&i*q[j]<=100000001;j++)
		{
			v[i*q[j]]=1; //筛掉	
			if(i%q[j]==0) break;//保证每个i*t.front() 只被筛一次
		}
	}
}
int main()
{
	oula();
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int l,r,ans=0;
		cin>>l>>r;
		int i=lower_bound(q,q+cnt,l)-q;
		for(;q[i]<=r;i++)
		{
			int o=q[i],sum=0;
			while(o!=0)
			{
				sum+=o%10;
				o/=10;
			}
			if(!v[sum]) ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}