10533

#include<stdio.h>
#include<math.h>

int main()
{
        int prime,num1,num2,a,c,tcase,sum,i,count,p,j;

	/********sieve******/
        int k, m[31250]={0}, n;
        int N = 1000000;
        m[0/32] = m[0/32] | 1 << 0%32;
        m[1/32] = m[1/32] | 1 << 1%32;
        for(k=3; k<=sqrt(N); k = k+2)
        {
            if( (m[k/32] & 1<<k) == 0 )
            {
                for(i=k*k; i<=N; i += 2*k )
                {
                    m[i/32] = m[i/32] | 1 << i%32;
                }
            }
        }
        for(i=4; i<=N; i += 2 )
        {
            if( (m[i/32] & 1<<i) == 0 )
            {
                m[i/32] = m[i/32] | 1 << i%32;
            }
        }
	/********************/


        scanf("%d",&tcase);
        while( tcase--)
        {
            scanf("%d %d",&num1,&num2);
            count = 0;
            for( prime = num1; prime <= num2; prime=prime+2)
            {
                if( prime%2 == 0 && prime > 2 && prime != 1 )
                {
                    prime = prime + 1;
                }

                    a = 1;
                    if (prime == 2)
                    {
                         count++;
                         prime = prime - 1;
                         continue;
                    }
                    else if (prime < 1)
                    {
                         continue;
                    }
                    else if (prime == 1)
                    {
                         count++;
                         continue;
                    }


                    if( (m[prime/32] & 1<<prime) == 0)
                    {
                        sum=0;
                        c = prime;
                        while ( c%10 != 0)
                        {
                            sum = sum + c%10;
                            c = c/10;
                            while ( c != 0 && c%10 == 0)
                            {
                                c = c/10;
                            }
                        }

                        if (sum < 2)
                        {
                             continue;
                        }
                        if( (m[sum/32] & 1<<sum) == 0)
                        {
                            count++;
                        }
                    }
            }
            printf("%d\n",count);
        }
        return 0;
}