HARSHAD - Devlali Numbers
Devlali numbers were an important coinage by Indian recreational mathematician 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
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 |