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
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