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 <= 10⁶
1 <= L <= R <= 10⁶