#include <bits/stdc++.h>
using namespace std;
#define maX 1000005
bool pm[maX];
int cnt[maX];
void sieve()
{
    int i,j,k,l;
    pm[0]=pm[1]=1;
    for(i=4;i<=maX;i+=2)
    {
        pm[i]=1;
    }
    for(i=3;i<=maX;i+=2)
    {
        if(pm[i]==0)
        {
            for(j=i*i;j<=maX;j+=i+i)
            {
                pm[j]=1;
            }
        }
    }
}
int sd(int n)
{
    int an=0,r;
    while(n>0)
    {
        r=n%10;
        an+=r;
        n/=10;
    }
    return an;
}
int main()
{
   int t,l,r,i,cn=0,m;
   sieve();
   for(i=0;i<=maX;i++)
   {
       m=sd(i);
       if(pm[i]==0 && pm[m]==0) cn++;
       cnt[i]=cn;
   }
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d %d",&l,&r);
       printf("%d\n",cnt[r]-cnt[l-1]);
   }
   return 0;
}