HARSHAD - Devlali Numbers

no tags 

Harshad 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 r+d(r)=m, then m is a Harshad number. First few Harshad numbers are 1,3,5,7.. so on.
A prime number falling in this family is called a Harshad Prime. First few Harshad 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 Harshad Primes in range [A,B] (both inclusive)
EXAMPLE
Input
3
1 3
0 10
5 8
Output
1
3
2

 

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