#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn = 79999999;
int T, L, R;
int prime[6761460], cnt1, dprime[3164990], cnt2;
bitset<Maxn> isprime;
//bool isprime[Maxn];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
bool check(int x){
	int sum = 0;
	while(x){	
		sum = sum + x % 10;
		x /= 10;
	}
	return isprime[sum] == false;
}
inline void Init(){
	isprime[1] = true;
	for(int i = 2; i <= Maxn - 1; i++){
		if(!isprime[i]) prime[++cnt1] = i;
		for(int j = 1; j <= cnt1 && i * prime[j] <= Maxn - 1; j++){
			isprime[i * prime[j]] = true;
			if(i % prime[j] == 0) break; 
		}
	}
	for(int i = 1; i <= cnt1; i++)
		if(check(prime[i])) dprime[++cnt2] = prime[i];
}
signed main(){
	Init();
	T = read();
	while(T--){
		L = read(), R = read();
		cout << (upper_bound(dprime + 1 ,dprime + 1 + cnt2, R) - dprime) - (lower_bound(dprime+1, dprime + 1 + cnt2, L) - dprime) << endl;
	} 
	return 0;
}