LUCIFER - LUCIFER Number


Lucifer is the only human whi has defeated RA-ONE in a computer game ..

RA-One is after lucifer for revenge and G-One is there to protect him ...

All thi G-One and Ra-one Nonsense has disturbed lucifers life..

He wants to get Rid of Ra-One and kill him . He found that Ra-One can be killed only by throwing Lucifer number of weapons at him.

Lucifer number  shares the some properties of Ra-One Numbers numbers and G-One Numbers

Any number is LUCIFER NUMBER  if the Difference between Sum of digits at even location and Sum of digits at odd location is prime number .. For eg... for 20314210 is lucifer number

digits at odd location 0,2,1,0

digits at even location 1,4,3,2

diff = (1+4+3+2)-(0+2+1+0)=10-3  = 7 ..... a prime number.

Lucifer has access to a Warehouse which has lots of weapons ..

He wants to know in how many ways can he kill him.

Can you help him?

 

Input

First line will have a number 't' denoting the number of test cases.

each of the following t lines will have 2 numbers 'a' , 'b'

Output

Print single number per test case, depicting the count of Lucifer numbers in the range a,b inclusive.

Example

Input:

5
200 250
150 200
100 150
50 100
0 50

 Output:
2
16
3
18
6


NOTE: t will be less than 100
from and to will be between 0 and 10^9 inclusive

hide comments
sieunhanbom04: 2017-03-20 16:58:19

:'( ACed. So good

sprof: 2016-07-24 23:25:00

Last edit: 2016-07-24 23:43:59
Liquid_Science: 2016-02-01 15:36:29

fastest in JAVA :P

ihak: 2015-07-25 14:34:58

Easy . Just Change the terminating condition in My Function and All the three problems are Done!
Well good setting anyways. I didnt see a lot of problems on spoj on Digit Dynamic Programming :)

Mitch Schwartz: 2015-02-06 22:45:33

@Ankur Tyagi: The ones digit is in odd position, the tens digit is in even position, the hundreds digit is in odd position, etc.

warlock: 2015-02-06 17:57:45

why output of Test case "0 50" is only 6. Answer should be 14. Corresponding numbers for this ans are : 13 14 16 18 24 25 27 29 35 36 38 46 47 49

Last edit: 2015-02-06 17:58:42
Gaurav Kumar Verma: 2014-10-23 21:14:57

few test cases that might help
input
2
0 1000000000
1 1000000000


output
130629858
130629858

free mind ;): 2014-08-19 23:53:30

DONE !!

Akash Agrawall: 2014-07-15 15:32:31

Never expected that I will be able to get it accepted. After two days of debugging over a silly issue. :)

Last edit: 2014-07-15 15:32:56
Darko Aleksic: 2012-08-21 22:31:26

Time limit seems to be too tight - can the problem setter submit a reference solution in one of the languages that has not been accepted yet? Say Java or Python. Otherwise, limit it to C/C++/Pas.


Added by:Devil D
Date:2012-03-09
Time limit:0.100s-0.5s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own