#include<bits/stdc++.h>
using namespace std;

const int N = 1e8 + 1;

int num;
vector < int > prime;
bitset < N > visit;
void Prime(){
	int nw=0;
	for (int i = 2;i <= N; i++) {
		if (!visit[i]) 
			prime.push_back(i) ,nw++,num++;
		for (int j = 1; j <= num && i*prime[j - 1] <= N; j++) {
			visit[i*prime[j - 1]] = 1; 
			if (i % prime[j - 1] == 0)break;
		}
	}
	return ;
}

int l , r;

int ans;

char ch[10];

int tot;

int len;

int T;

short work(int m)
{
	tot = 0;
	
	sprintf(ch , "%d" , m);
	
	len = strlen(ch);
	
	for(int i = 0;i < len;i ++)
		tot += ch[i] - '0';
	
	return tot;
}

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*10+ch-48;ch=getchar();}
	return x*f;
}

main()
{
	Prime();
	
//	for(int i = 1;i <= 100;i ++)
//		if(! visit[i])
//			cout << i << ' ';

	visit[1] = true;
	
	T = read();
	
	while(T --)
	{
		l = read() , r = read();
		
		ans = 0;
		
		for(int i = l;i <= r;i ++)
			if(visit[i])
				continue;
		else if(! visit[work(i)])
			ans ++;
		
		cout << ans << '\n';
	}
}