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
hacker_sk:
20181230 12:57:10
AC in two GO :P 

sdssudhu:
20180124 17:52:18
AC in one GO;) 

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.. 
Added by:  Devil D 
Date:  20120224 
Time limit:  0.171s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 