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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor