Description

A prime number is a natural number greater than $1$ that has no divisors other than $1$ and itself. A double prime is defined as a prime number whose sum of digits is also a prime number. Given a closed interval, determine how many double primes are in this interval.

Input Format

The input contains multiple sets of testdata.

The first line contains an integer $T$, representing the number of test cases. Each of the next lines contains one test case, with two integers $L$ and $R$ separated by a space.

Output Format

For each test case, output one line containing an integer, representing the number of double primes in the closed interval $[L,\ R]$.

4
3 3
4 4
1 5
1 15

1
0
3
5

Hint

Sample explanation.

From $1$ to $15$, there are $6$ prime numbers: $2$, $3$, $5$, $7$, $11$, $13$. For the first five primes, the sum of digits is also prime, so they are all double primes. The sum of digits of the prime $13$ is $4$, which is not prime, so $13$ is not a double prime.

Constraints.

• Subtask $1$: $1 \le L \le R \le 10^2$, $10$ points.
• Subtask $2$: $1 \le L \le R \le 10^4$, $20$ points.
• Subtask $3$: $1 \le L \le R \le 10^6$, $60$ points.
• Subtask $4$: $1 \le L \le R \le 10^8$, $10$ points.

For $100\%$ of the data, $1 \le T \le 100$.

Hint (the data has been strengthened).

The last subtask requires your program to have high space efficiency and time efficiency, otherwise it is easy to exceed the memory limit or time limit.

Translated by ChatGPT 5