[UVA10533]Digit

A prime number is a positive number, which is divisible by exactly two diﬀerent integers.

A digit prime is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime because 4 + 1 = 5 and 5 is a prime number. 17 is not a digit prime because 1 + 7 = 8, and 8 is not a prime number.

In this problem your job is to ﬁnd out the number of digit primes within a certain range less than 1000000.

Input

First line of the input ﬁle contains a single integer N (0 < N ≤ 500000) that indicates the total number of inputs. Each of the next N lines contains two integers t1 and t2 (0 < t1 ≤ t2 < 1000000).

Output

For each line of input except the ﬁrst line produce one line of output containing a single integer that indicates the number of digit primes between t1 and t2 (inclusive).

Sample Input

3 10 20 10 100 100 10000

Sample Output

1 10 576

Note: You should at least use scanf() and printf() to take input and produce output for this problem. cin and cout is too slow for this problem to get it within time limit.

透過線性篩法劍質數表，再透過DP存即可。

//使用Java的考生請注意，最外層的類別(class)需命名為 main 。 
//如果遇到超乎想像的狀況，請更改編譯器試看看!! 各編譯器特性不同!! 
//預設測資、隨機測資、固定測資是用來幫助除錯用的。批改時，只看暗中測資是否通過!! 
#include <stdio.h>; 
#include <stdlib.h>; 
#include <string.h>; 
bool prime[1000005]; 
int dp[1000005] = {0}; 
void sieve() { 
  for(int i = 0 ; i < 1000005 ; ++i) { 
    prime[i] = true; 
  } 
  prime[0] = false; 
  prime[1] = false; 
  for(int i = 2 ; i <= 1000 ; ++i) { 
    if(!prime[i]) continue; 
    for(int j = 2 ; i * j <= 1000005 ; ++j) { 
      prime[i * j ] = false; 
    } 
  } 
  /*
  for(int i = 0 ; i < 10000 ; ++i) { 
    if(prime[i]) printf("%d ",i); 
  }*/ 
} 
void check() { 
  for(int i = 1 ; i < 1000005 ; ++i) { 
    dp[i] = dp[i-1]; 
    if(!prime[i])continue; 
    //printf("* %d\\n",i); 
    char temp[7] = {0}; 
    int sum = 0; 
    sprintf(temp,"%d",i); 
    for(int i = 0 ; i < strlen(temp) ; ++i) { 
      sum += temp[i] - '0'; 
    } 
    //printf("sum %d\\n",sum); 
    if(prime[sum]) { 
      dp[i]++; 
      //printf("dp %d i %d\\n",dp[i],i); 
    }
  } 
} 
int main() { 
  sieve(); 
  check(); 
  int n = 0; 
  int a1,a2; 
  scanf("%d",&n); 
  while(n--) { 
    scanf("%d %d",&a1,&a2); 
    printf("%d\\n",dp[a2]- dp[a1-1]); 
  } 
return 0; 
}