I am stuck in this problem. Pls help me out.

Here is the problem :-

A prime number is a positive number, which is divisible by exactly two different 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 find out the number of digit primes within a certain

range less than 1000000.

Input

First line of the input file 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 first 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