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
2024-09-16 16:03:11
nice
2023-07-05 19:37:24
lol people celebrating in the comment section trying to flex newbies
2023-03-31 22:55:02
WOWOWO
2021-12-25 14:43:35 [Rampage] Blue.Mary
SIGILL and SIGKILL are not the same (Runtime Error) signal. Pay attention!
2021-12-25 11:26:08
Don't use pragma or you will get SIGKILL
2020-06-25 06:54:58
Fine fn ally
2020-06-04 10:40:16
No one cares in how many attempts you did :)
2020-04-11 11:55:30
1st digit DP AC in one go :)
2019-11-23 09:52:18
Easy digit dp problem
my 4th digit dp
2019-09-09 09:41:30
Down voted because too ez.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.