Nafeeur

/****************************************************
 * Author      : Kaidul Islam
 * University  : Khulna University of Engr. and Tech.
*****************************************************/
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(__typeof(n) i = 0; i < (n); i++)
#define rrep(i, n) for(__typeof(n) i = (n) - 1; i >= 0; --i)
#define rep1(i, n) for(__typeof(n) i = 1; i <= (n); i++)
#define FOR(i, a, b) for(__typeof(b) i = (a); i <= (b); i++)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define INF (1 << 30)
#define PI acos(-1.0)
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof x)
#define eps 1e-9
#define pii pair<int, int>
#define couple make_pair
#define X first
#define Y second
#define vi vector<int>
#define vpii vector< pii >
#define si set<int>
#define SDi(x) sf("%d", &x)
#define SD2(x, y) sf("%d %d", &x, &y)
#define SD3(x, y, z) sf("%d %d %d", &x, &y, &z)
#define SDs(x) sf("%s", x)
#define pf printf
#define print(x) pf("%d ", x)
#define println(x) pf("%d\n", x)
#define output(x, y); pf("Case %d: %d", ++x, y)
#define newLine pf("\n")
#define sf scanf
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#if ( _WIN32 or __WIN32__ )
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define SDl(x) sf(LLD, &x)
#define MAX5 100000
#define MAX7 10000000
#define MAX9 1000000000
#define MOD7 (MAX7 + 7)
#define MOD9 (MAX9 + 9)
typedef long long i64;
typedef unsigned long long ui64;
const i64 INF64 = (i64)1E18;

class TimeTracker {
    clock_t start, end;
public:
    TimeTracker() {
        start = clock();
    }
    ~TimeTracker() {
        end = clock();
        fprintf(stderr, "%.3lf s\n", (double)(end - start) / CLOCKS_PER_SEC);
    }
};

/** Implementation **/

#define Max 1000001
int prime[(Max / 32) + 2];
int sum[Max + 10];

int getDigitSum(int n) {
    int ans = 0;
    while(n) {
        ans += (n % 10);
        n /= 10;
    }
    return ans;
}

int main(void) {
#ifndef ONLINE_JUDGE
//     READ("in.txt");
//     WRITE("out.txt");
#endif
    int tcase, caseNo = 0;
    SDi(tcase);
    int t1, t2;
    // pre-processing
    int sqrtN = sqrt(Max);
    int i = 0;
    prime[i >> 5] |= (1 << (i & 31));
    ++i;
    prime[i >> 5] |= (1 << (i & 31));
    for(i = 3; i <= sqrtN; i += 2) {
        if( !(prime[i >> 5] & (1 << (i & 31))) ) {
            for(int j = i * i; j <= Max; j += (i << 1)) {
                prime[j >> 5] |= (1 << (j & 31));
            }
        }
        prime[(i + 1) >> 5] |= (1 << ((i + 1) & 31));
    }
    int offset = (sqrtN & 1) ? sqrtN + 1 : sqrtN;
    for(int k = offset; k <= Max; k += 2) {
        prime[k >> 5] |= (1 << (k & 31));
    }

    sum[0] = sum[1] = 0;
    int cnt = 0;
    sum[2] = ++cnt;
    for(int i = 3; i <= Max; i += 2) {
        if( !(prime[i >> 5] & (1 << (i & 31))) ) {
            int ret = getDigitSum(i);
            if( !(prime[ret >> 5] & (1 << (ret & 31))) ) ++cnt;
        }
        sum[i] = sum[i + 1] = cnt;
    }

    int ans;
    while(tcase--) {
        SD2(t1, t2);
        ans = sum[t2] - sum[t1 - 1];
        println(ans);
    }
    return EXIT_SUCCESS;
}