optimus-prime-2

Little Sam has a special liking for numbers as well as the famous Movie and TV-Series TRANSFORMERS.
He has a weird perspective of seeing numbers. He considers all the numbers as Transformers. But out of all transformers, he likes one of the transformers the most, the Leader of Autobots – Optimus Prime.
Now he has given all numbers some or other category, in form of names of transformers, i.e. some numbers may be Hotshot or some may be IronHide or StarScream or Megatron and so on.
Obviously some of these numbers would be his favourite, Optimus Prime. Optimus Primes are special numbers which qualify certain strict conditions.

A number N is an Optimus Prime, if the number itself is Prime and it contains prime number of prime digits in it.

Ex. N=23 Now N is prime and it contains 2 (prime number of) prime digits in it, 2 and 3. Hence N is an Optimus Prime as 2 is prime and the number 23 itself is a prime.

Ex. N=43 Though N is prime,it contains only 1 prime(i.e 3). It doesn’t contain prime number of prime digits in it as 1 is not prime. So N isn’t an Optimus Prime as 1 is not a prime though 43 is a prime.

So now, as numbers are infinite Sam can’t find all the Optimus Primes, but given a range of numbers, he wonders how many Optimus Primes are present in it.
Our task is to find out the number of Optimus Primes in the given range of numbers.

INPUT: The first line of input contains an integer T specifying the number of test-cases. Next T lines contain two integers M and N indicating the starting and ending point of the range.

CONSTRAINTS

T ≤ 100

M ≤ N ≤ 10^12

(N-M) ≤ 1000000

OUTPUT: For each test case, print one line, specifying the number of Optimus Primes in the range.

SAMPLE INPUT
4
1 10
10 25
20 75
131 141

SAMPLE OUTPUT
0
1
4
1

Explanation

Case 1 *: No Optimus Primes in range from 1 to 10
*Case 3 **: 23, 37, 53, 73 are the Optimus Primes in range from 20 to 75.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: