LUCIFER - LUCIFER Number


Lucifer is the only human who 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 Lucifer's 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 example, 20314210 is a Lucifer number:

digits at odd location 0, 2, 1, 0.

digits at even location 1, 4, 3, 2.

difference = (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. 'a' and 'b' will be between 0 and 10^9 inclusive.


hide comments
anuragdw0710: 2023-04-16 16:49:54

If any one is struck with dp part first solve "Ra-One Numbers" on spoj.

dpw4112001: 2021-11-20 16:17:51

This problem is pretty unclear. Got AC after a lot of considerations which are not mentioned.

biber_2222: 2021-10-25 19:15:51

this is giving tle for python code even after memoization

rangey_18o3_20: 2021-09-15 17:39:39

AC in 1 go. it's a great feeling

manujk: 2020-11-17 10:38:12

Read @iceelement comment for further clarification of the problem. Though the problem is easy, the statement is a bit incomplete.

Last edit: 2020-11-17 10:38:52
manish_thakur: 2020-05-24 05:52:50

Why does this always involve Ra one and G one

saurav_555: 2020-03-26 22:02:09

After solving GONE AND RAONE....
like Easy peasy...

bhagirathi08: 2019-09-08 11:10:03

My 2nd digit dp problem, AC in one go HOLLAHhhhhh.....

iceelement: 2019-01-25 03:56:21

I think this question requires further clarifications. Difference here means the signed difference between even and odd positions. The positioning is considered from right to left with 1 based indexing. Negative numbers are not considered prime, even if their absolute value is prime.

puddin: 2018-07-05 01:01:38

Can someone pls explain how the ans for test case-- 0 50 is 6 as I am getting 14 for it.


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