GONE - G-One Numbers

The War of Evil vs Good continues and Ra-One and G-One continue to be on respective sides.

After saving all the cities with Ra-One Numbers G-One realised that some cities whose population is a "G-One Number" can be easy target for Ra-One.

A G-One number is a number sum of whose digits is a prime number

For eg. 12 .. sum = 1+2 =3 ... 3 is a prime number.

G-One wants to find out all the populations which can be g-One 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 G-One Numbers.


first line has number 'c' indicating the number of ranges.

'c' lines follow and contain two numbers ..... 'f' and 't' inclusive.


Print a single line per case giving the number of populations which are G-One numbers.


10 19
1 9
20 29


Note: c will be less than 100
t and f will be less than 10^8 inclusive

hide comments
pratham_1: 2017-09-07 15:59:56

AC in one GO;)

Vivek Mangal: 2016-04-08 22:48:01

very nice problem

Medo: 2015-08-22 22:52:22

One of the best problems I solved.

parijat bhatt: 2015-05-31 06:42:34

Both numbers are inclusive.

Gaurav Kumar Verma: 2014-10-21 08:48:59

worst case Test Case
1 100000000

lifeofpie: 2014-09-13 14:15:19

@All can any one tell me why i m getting runtime error SIGKILL after runtime(2) ...

super human: 2014-05-26 14:08:47

nice one!!

AAYUSH KUMAR: 2014-05-10 03:41:54

just luved it..

shivendra panicker: 2012-12-15 16:17:04

nice problm :)deceptive!

Muhammed Hedayetul Islam: 2012-10-17 21:31:38

@Ravi Kiron: You can simply check the first sample input to be verified about 1

Added by:Devil D
Time limit:1s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64