Problem A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky?

Input: The first line contains the number of test cases T. Each of the next T lines contains two integers, A and B.

Output: Output T lines, one for each case containing the required answer for the corresponding case.

Constraints:
1 <= T <= 10000
1 <= A <= B <= 10^18

Sample Input:

2

1 20

120 130

Sample Output:

4

1

Explanation: For the first case, the lucky numbers are 11, 12, 14, 16. For the second case, the only lucky number is 120.

The problem is quite simple if we use brute force, however the running time is so critical that my program failed most test cases. My current idea is to use dynamic programming by storing the previous sum in a temporary array, so for example:
sum_digits(10) = 1 -> sum_digits(11) = sum_digits(10) + 1
The same idea is applied for sum square but with counter equals to odd numbers. Unfortunately, it still failed 9 of 10 test cases which makes me think there must be a better way to solve it. Any idea would be greatly appreciated.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cassert>
#include <bitset>

using namespace std;

bool prime_table[1540] = {
    0, 0, 1, 1, 0, 1, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0 
};

unsigned num_digits(long long i) {
    return i > 0 ? (long) log10 ((double) i) + 1 : 1;
}

void get_sum_and_sum_square_digits(long long n, int& sum, int& sum_square) {
    sum = 0;
    sum_square = 0;
    int digit;
    while (n) {
        digit = n % 10;
        sum += digit;
        sum_square += digit * digit;
        n /= 10;
    }
}

void init_digits(long long n, long long previous_sum[], const int size = 18) {
    int current_no_digits = num_digits(n);
    int digit;
    for (int i = 0; i < current_no_digits; ++i) {
        digit = n % 10;
        previous_sum[i] = digit;
        n /= 10;
    }   

    for (int i = current_no_digits; i <= size; ++i) {
        previous_sum[i] = 0;
    }   
}

void display_previous(long long previous[]) {
    for (int i = 0; i < 18; ++i) {
        cout << previous[i] << ",";
    }
}

int count_lucky_number(long long A, long long B) {
    long long n = A;
    long long end = B;
    int sum = 0;
    int sum_square = 0;
    int lucky_counter = 0;

    get_sum_and_sum_square_digits(n, sum, sum_square);

    long long sum_counter = sum;
    long long sum_square_counter = sum_square;

    if (prime_table[sum_counter] && prime_table[sum_square_counter]) {
        lucky_counter++;
    }

    long long previous_sum[19] = {1};

    init_digits(n, previous_sum);

    while (n < end) {
        n++;
        if (n % 100000000000000000 == 0) {
            previous_sum[17]++;
            sum_counter = previous_sum[17] + previous_sum[18];
            sum_square_counter = previous_sum[17] * previous_sum[17] + previous_sum[18] * previous_sum[18];

            previous_sum[16] = 0;
            previous_sum[15] = 0;
            previous_sum[14] = 0;
            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000000000000 == 0) {
            previous_sum[16]++;
            sum_counter = previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[15] = 0;
            previous_sum[14] = 0;
            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000000000000 == 0) {
            previous_sum[15]++;

            sum_counter = previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[14] = 0;
            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000000000000 == 0) {
            previous_sum[14]++;

            sum_counter = previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000000000 == 0) {
            previous_sum[13]++;

            sum_counter = previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000000000 == 0) {
            previous_sum[12]++;

            sum_counter = previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000000000 == 0) {
            previous_sum[11]++;

            sum_counter = 
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000000 == 0) {
            previous_sum[10]++;

            sum_counter = 
                previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000000 == 0) {
            previous_sum[9]++;

            sum_counter = 
                previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];


            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000000 == 0) {
            previous_sum[8]++;

            sum_counter = 
                previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000 == 0) {
            previous_sum[7]++;

            sum_counter = 
                previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000 == 0) {
            previous_sum[6]++;

            sum_counter = 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000 == 0) {
            previous_sum[5]++;

            sum_counter = previous_sum[5] + previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] + previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000 == 0) {
            previous_sum[4]++;

            sum_counter = 
                previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000 == 0) {
            previous_sum[3]++;

            sum_counter = 
                previous_sum[3] + previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[3] * previous_sum[3] +
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100 == 0) {
            previous_sum[2]++;

            sum_counter = 
                previous_sum[2] + previous_sum[3] + previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[2] * previous_sum[2] +
                previous_sum[3] * previous_sum[3] +
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10 == 0) {
            previous_sum[1]++;

            sum_counter = 
                previous_sum[1] + previous_sum[2] + previous_sum[3] + previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[1] * previous_sum[1] + 
                previous_sum[2] * previous_sum[2] +
                previous_sum[3] * previous_sum[3] +
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[0] = 0;
        }
        else {
            sum_counter++;
            sum_square_counter += ((n - 1) % 10) * 2 + 1;
        }

        // get_sum_and_sum_square_digits(n, sum, sum_square);
        // assert(sum == sum_counter && sum_square == sum_square_counter);
        if (prime_table[sum_counter] && prime_table[sum_square_counter]) {
            lucky_counter++;
        }
    }

    return lucky_counter;
}


void inout_lucky_numbers() {
    int n;
    cin >> n;

    long long a;
    long long b;

    while (n--) {
        cin >> a >> b;
        cout << count_lucky_number(a, b) << endl;
    }
}

int main() {
    inout_lucky_numbers();

    return 0;
}