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
scolar_fuad:
20191123 09:52:18
Easy digit dp problem


gs0812:
20190909 09:41:30
Down voted because too ez.


bhagirathi08:
20190908 16:02:19
4th digit dp AC in one go 

zingme123aptx:
20190528 09:47:26
trâu cũng ac 

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