GONE  GOne Numbers
The War of Evil vs Good continues and RaOne and GOne continue to be on respective sides.
After saving all the cities with RaOne Numbers GOne realised that some cities whose population is a "GOne Number" can be easy target for RaOne.
A GOne number is a number sum of whose digits is a prime number
For eg. 12 .. sum = 1+2 =3 ... 3 is a prime number.
GOne wants to find out all the populations which can be gOne numbers....
Can You help Him.?
You will be given the range of population and you have to tell him how many in this range are GOne Numbers.
Input
first line has number 'c' indicating the number of ranges.
'c' lines follow and contain two numbers ..... 'f' and 't' inclusive.
Output
Print a single line per case giving the number of populations which are GOne numbers.
Example
Input: 3
10 19
1 9
20 29
Output:
4
4
5
Note: c will be less than 100
t and f will be less than 10^8 inclusive
hide comments
pratham_1:
20170907 15:59:56
AC in one GO;) 

Vivek Mangal:
20160408 22:48:01
very nice problem


Medo:
20150822 22:52:22
One of the best problems I solved. 

parijat bhatt:
20150531 06:42:34
Both numbers are inclusive. 

Gaurav Kumar Verma:
20141021 08:48:59
worst case Test Case


lifeofpie:
20140913 14:15:19
@All can any one tell me why i m getting runtime error SIGKILL after runtime(2) ...


super human:
20140526 14:08:47
nice one!! 

AAYUSH KUMAR:
20140510 03:41:54
just luved it.. 

shivendra panicker:
20121215 16:17:04
nice problm :)deceptive! 

Muhammed Hedayetul Islam:
20121017 21:31:38
@Ravi Kiron: You can simply check the first sample input to be verified about 1 
Added by:  Devil D 
Date:  20120224 
Time limit:  1s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 