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

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 G-One 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


Added by:Devil D
Date:2012-02-24
Time limit:1s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2014-05-10 03:41:54 AAYUSH KUMAR
just luved it..
2012-12-15 16:17:04 shivendra panicker
nice problm :)deceptive!
2012-10-17 21:31:38 Muhammed Hedayetul Islam
@Ravi Kiron: You can simply check the first sample input to be verified about 1
2012-09-22 08:14:27 Ravi Kiran
Maybe quite obvious, but still to prevent any cause of WA for others -
0, 1 are treated as composite (or non-prime).
2012-07-22 18:33:19 (Tjandra Satria Gunawan)(曾毅昆)
@15972125841321: I've made some experiment and found that the max values is 115.000.000 not 10^9.
2012-07-15 10:35:37 15972125841321
IS your range correct because i am getting segfault ... when i used assert to check for input values the t&f were greater than 10^8 or less than 0... are the values of input ranges higher than 10^8??

the values are in the range 10^9... plz update it..

Last edit: 2012-07-15 10:45:00
2012-05-29 16:57:08 Aman Kumar
awesome problem ! :)
2012-05-17 09:36:39 Neel Lahiri
how to get rid of TLE?
2012-03-09 07:35:02 Devil D
Added some more test cases and rejudged ....
1 solution went from AC to WA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.