Chandu is a big fan of primes. He defines another kind of primes alpha-primes. Alpha-primes are defined as primes for which there exists some suffix of a given number which is a prime. For example, 12 is not prime but 12 is alpha prime as there exists a suffix which is a prime. In case of 12, 2 is prime therefore 12 is alpha-prime.
Now, he gives you Q queries of the form L R for which you have to calculate how many alpha-primes are there in the range [L, R].
Input :
First line contains a single integer Q denoting no. of queries.
Next Q line contains two space separated integers L and R.
Output :
For each query output the count of alpha-primes in the range [L, R]
Constraints :
1 <= Q <= 106
1 <= L <= R <= 106
Query 1 2
1 is neither prime nor alpha-prime.
2 is prime and there exists a suffix which is 2 itself which is prime therefore 2 is alpha-prime.
Therefore total count in range 1 2 is 1.
Query 10 14
10 is not aplha-prime as its suffix 0 and 10 are not prime.
11 is alpha-prime as its suffix 11 is prime.
12 is alpha-prime as its suffix 2 is prime.
13 is alpha-prime as its suffix 3 is prime.
14 is not alpha-prime as its suffix 4 and 14 are not prime.
Therefore total count in range 10 14 is 3.
