#前缀和预处理开不了1e8，一开就全MLE，望大佬解救

#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int N = 1e8;
bitset<N> isprime; 
int cnt , q , l , r;
int f[N];
int prime[N >> 1];
inline int F(int x){
	int sum = 0;
	while(x) sum += x % 10 , x /= 10;
	return sum;
}
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;
}
inline void print(int x){
	if(x < 0) putchar('-') , x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
int main(){
	isprime.set();
	isprime[1] = 0;
	for(register int i = 2;i <= 1e8;i++){
		if(isprime[i]) prime[++cnt] = i;
		for(register int j = 1;i * prime[j] <= 1e8 && j <= cnt;j++){
			isprime[i * prime[j]] = 0;
			if(i % prime[j] == 0) break;
		}
	}	
	f[1] = 0;
	for(register int i = 2;i <= 1e7;i++){
		if(isprime[i] && isprime[F(i)]) f[i] = f[i - 1] + 1;
		else f[i] = f[i - 1];
	}
	q = read();
	while(q--){
		l = read() , r = read();
		print(f[r] - f[l - 1]);
		putchar('\n');
	}
	return 0;
}