Digit Prime

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#define IN freopen("f:\\in.txt", "rt", stdin);
#define OUT freopen("f:\\out.txt", "wt", stdout);
#define FOR(n) for(int i = 0; i < n; i++)
#define ll long long int
#define STESTCASE int t;scanf("%d", &t);getchar();for(int tc = 1; tc <= t; tc++)
#define TESTCASE int t;scanf("%d", &t);for(int tc = 1; tc <= t; tc++)
#define PF printf
#define SF scanf
#define EP 0.000000001
#define MAX 10000009
#define DEBUGG printf("DEBUGG\n");
using namespace std;

int n = 1000009;
int prime[1000009];
int gen[1000009];

int set_bit(int n, int position)
{
    return n | (1 << position);
}
bool get_bit(int n, int position)
{
    return n & (1 << position);
}

void generate_prime()
{
    int i, j, root = sqrt(n);

    prime[0] = set_bit(prime[0], 0);
    prime[0] = set_bit(prime[0], 1);

    for(i = 4; i <= n; i += 2) prime[i >> 5] = set_bit(prime[i >> 5], i & 31);

    for(i = 3; i <= root; i++)
        if(!get_bit(prime[i >> 5], i & 31))
            for(j = i * i; j <= n; j += i+i)
                prime[j >> 5] = set_bit(prime[j >> 5], j & 31);

//    for(i = 0; i < 100; i++)
//        if(!get_bit(prime[i >> 5], i & 31))
//            cout << i << ' ';
//    cout << endl;
}

void pregen()
{
    for(int i = 0; i <= n; i++)
    {
        if(!get_bit(prime[i >> 5], i & 31))
        {
            int num = i, temp = 0;
            while(num > 0)
            {
                temp += num % 10;
                num /= 10;
            }
            //cout << temp << ' ';

            if(!get_bit(prime[temp >> 5], temp & 31))
            {
                gen[i] = gen[i-1] + 1;
            }
            else gen[i] = gen[i-1];
        }
        else gen[i] = gen[i-1];

        //cout << i << ' ' << gen[i] << endl;
        //DEBUGG
    }
    //cout << gen[89] << endl;
}


int main()
{
    //IN OUT
    generate_prime();
    pregen();
    //cout << gen[100000] << endl;
    TESTCASE
    {
        int a, b;
        SF("%d %d", &a, &b);
        if(a == b)
        {
            if(!get_bit(prime[a >> 5], a & 31))
            {
                int sum = 0;
                while(a > 0)
                {
                    sum += a % 10;
                    a /= 10;
                }
                if(!get_bit(prime[sum >> 5], sum & 31)) cout << 1 << endl;
                else cout << 0 << endl;
            }
            else cout << 0 << endl;
        }
        else if(get_bit(prime[a >> 5], a & 31)) PF("%d\n", gen[b] - gen[a]);
        else PF("%d\n", (gen[b] - gen[a]) + 1);
    }


    return 0;
}