HARSHAD - Devlali Numbers

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

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

hide comments
2014-12-25 15:15:19 Jugal kishor sahu
easy one.....sieve
2014-01-11 19:04:19 P_Quantum
Finally done..!! Good ques.
2014-01-11 14:51:48 BLANKRK
good one.
2013-11-27 15:43:01 Sourangsu
Awesome Question...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.