hdu 4548

#include<stdio.h>
int a[1000001],b[40001];
int main()
{
    int i,j,n,m,k,sum,num,t,c,d,op=1;
    num=0;
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==1)continue;
         k=i;sum=0;
         while(k)
         {
             sum+=k%10;
             k/=10;
         }
         if(a[sum]==0)
            b[num++]=i;
        for(j=i+i;j<=1000000;j+=i)
            a[j]=1;
    }
    /*for(i=0;i<100;i++)
        printf("%d ",b[i]);
    printf("
%d
",num);*/
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&c,&d);
        sum=0;
        for(i=0;i<num;i++)
        {
            if(b[i]>=c&&b[i]<=d)
                sum++;
            else if(b[i]>d)break;
        }
        printf("Case #%d: ",op++);
            printf("%d
",sum);
    }

    return 0;
}