P7588 Double Primes (2021 CoE-II A)

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.

**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.

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

**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