{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.\nA digit prime is number who is prime and the sum of it\u0027s digits is also prime.\nFor example, the prime number 41 is a digit prime because 4 + 1 \u003d 5 and 5 is a prime number. 17 is not a digit prime because 1 + 7 \u003d 8, and 8 is not a prime number. In this problem your job is to find out the number of digit primes within a certain range less than 1000000."}},{"title":"Input","value":{"format":"PLAIN","content":"First line of the input file contains a single integer N (0 \u003c N ≤ 500000) that indicates the total number of inputs. Each of the next N lines contains two integers r1 and r2 (0 \u003c r1 ≤ r2 \u003c 1000000)."}},{"title":"Output","value":{"format":"PLAIN","content":"For each line of input except the first line produce one line of output containing a single integer that indicates the number of digit primes between r1 and r2 (inclusive)."}},{"title":"Sample Input","value":{"format":"PLAIN","content":"3\n10 20\n10 100\n100 10000"}},{"title":"Sample Output","value":{"format":"PLAIN","content":"1\n10\n576"}},{"title":"Note!","value":{"format":"PLAIN","content":"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."}}]}