#include<bits/stdc++.h>
using namespace std;
int n;
bool p[130000000];
void eratos(int n) {
    int i,j;
    p[0]=p[1]=false;
    for(int i=2; i<=n; i++) p[i]=true;
    for(int i=2; i*i<=n; i++) {
        if(p[i]) {
            for(int j=i*i; j<=n; j+=i) {
                p[j]=false;
            }
        }
    }
}
int main(){
	scanf("%d",&n);
	eratos(10000000);
	for(int i=0;i<n;i++){
		int l,r,ans=0;
		scanf("%d%d",&l,&r);
		for(int j=l;j<=r;j++){
			if(p[j]){
				int u=j,ws=0;
				while(u>0){
					ws+=u%10;
					u/=10;
				}
				if(p[ws]) ans++;
			}
		}
		cout<<ans<<endl;
	}
}

90分