UVa 10533

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

typedef long long int       ll;
typedef unsigned long long int  ull;
typedef vector<int>         vi;
typedef vector<ll>          vll;
typedef vector<vi>          vvi;
typedef pair<int,int >      pii;
typedef vector< pii >       vpii;
typedef set<int>            sti;

#define sc                  scanf
#define pf                  printf
#define sci(n)              scanf("%d",&n)
#define scl(n)              scanf("%lld",&n)
#define scf(n)              scanf("%lf",&n)
#define scs(s)              scanf("%s",s)
#define pfi(n)              printf("%d",n)
#define pfl(n)              printf("%lld",n)
#define pff(n)              cout<<n
#define line                printf("\n")
#define spc                 printf(" ")
#define loop(i,x,y)         for(int i=int(x); i<=int(y); i++)
#define rloop(i,y,x)        for(int i=int(y); i>=int(x); i--)
#define cspf(i)             printf("Case %d: ", i)
#define pb                  push_back
#define mp                  make_pair
#define ff                  first
#define ss                  second
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define read()              freopen("input.txt", "r", stdin)
#define write()             freopen("output.txt", "w", stdout)
/// Constants
#define eps                 1e-9
#define PI                  acos(-1.0)  // 3.1415926535897932

vi chk(1000009);
vi cnt(1000009);


void seive(){
    chk[0]=1;
    chk[1]=1;
    for(int i=2;i<=1000001;i++){
        if(chk[i]==1)
            continue;
        for(int j=2;i*j<=1000001;j++){
            chk[i*j]=1;
        }
    }
}

int sum(int i)
{
    int sm=0;
    while(i>0){
        sm+=(i%10);
        i/=10;
    }
    return sm;
}

void prec()
{
    int c=0;
    loop(i,0,1000001){
        if(chk[i]==0){
            int dgsm=sum(i);
            if(chk[dgsm]==0){
                c++;
            }
        }
        cnt[i]=c;
    }
}

int main()
{
    seive();
    prec();
    int t;sci(t);
    int pcnt;
    loop(i,1,t){
        int x,y;
        sci(x);sci(y);
        if(x==0){
            pcnt=cnt[y];
        }
        else{
            pcnt=cnt[y]-cnt[x-1];
        }
        pfi(pcnt);line;
    }
    return 0;
}