HARSHAD - Devlali Numbers

no tags 

Devlali numbers were an important coinage by Indian recreational mathemtician D. R. Kaprekar.

For any positive integer n, define d(n) as the sum of n and the digits of n. Eg, d(199) = 199 + 1 + 9 + 9 = 218.

For a positive number m, if there exists no positive number r such that d(r) = m, then m is a Devlali number. First few Devlali numbers are 1, 3, 5, 7, ... so on.

A prime number falling in this family is called a Devlali Prime. First few Devlali Primes are 3, 5, 7, ... so on.

Input

First line contains integer Q

Next Q lines contain two integers A and B

Output

print Q lines, each listing number of Devlali Primes in range [A,B] (both inclusive)

Limits

1 <= Q <= 100000

0 <= A <= B <= 1000000

Example

Input
3
1 3
0 10
5 8

Output
1
3
2

hide comments
nadstratosfer: 2018-02-12 05:25:56

Good problem. Applied several ideas after the first AC, surprised to find out what worked here and what did not. Strangely, problem very much in style of the other Piyush Kumar, from Delhi.

sahil_420420: 2016-03-19 17:04:47

more testcases please with some big nmbers,testcase 5 wrong

sarthak gupta: 2015-10-23 10:40:25

good question....using stl the code length reduces to 1/4... :)

Jugal kishor sahu: 2014-12-25 15:15:19

easy one.....sieve

P_Quantum: 2014-01-11 19:04:19

Finally done..!! Good ques.

BLANKRK: 2014-01-11 14:51:48

good one.

Sourangsu : 2013-11-27 15:43:01

Awesome Question...


Added by:Piyush Kumar
Date:2012-09-21
Time limit:2.175s-5.438s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All