#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;
#define ll long long
const ll MAXFOR=1e8;
const ll MAXN=MAXFOR+18;
ll t,l,r;
vector<ll> isp,prm;
bitset<MAXN> bits;
ll add(ll x){
	ll ans=0;
	while(x){
		ans+=x%10;
		x/=10;
	}
	return ans;
}
int main(){
	bits.set(0);bits.set(1);
	for(int i=2;i<=MAXFOR;++i){
		if(!bits[i]) isp.push_back(i);
		for(int j=0;j<isp.size()&&isp[j]*i<=MAXFOR;++j){
			bits.set(isp[j]*i);
			if(i%isp[j]==0) break;
		}
	}
	for(int i=0;i<isp.size();++i) if(!bits[add(isp[i])]) prm.push_back(isp[i]);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld %lld",&l,&r);
		printf("%d\n",upper_bound(prm.begin(),prm.end(),r)-prm.end()-(lower_bound(prm.begin(),prm.end(),l)-prm.end()));
	}
	return 0;
}

rt