* And Naughty Numbers
*, our favourite footballer, supports Indian National Football Team. Being so, he is desperate to attend the grand unveiling of Igor Štimac, as the next manager of the club. But his arch-nemesis Lorenzo Buffon wants him to fail. Knowing that * is weak at mathematics, has given him a problem to solve before the ceremony. Can you help * do it and thwart the evil plans of Buffon?
A naughty number is one whose number of distinct prime factors is equal to the number of digits in its decimal representation. The number 1 is considered a naughty number.
Given Q queries, each query specifying two integers a and b, find the number of naughty numbers lying between a and b(both included).
Input Format
The first line contains an integer Q denoting the number of queries.Each of the next Q lines consists of two integers a and b denoting the range for this query.
Output Format
Print Q lines. The ith line consists the answer for the ith query.
Constraints
- 1 <= Q <=50,000
- 1 <= a = b <= 100,000
Sample Input
3
1 10
55 59
100 105
Sample Output
9
4
2
Explanation
In the range of 1-10, all the numbers except 6 are naughty numbers. In the range 55-59, the naughty numbers are 55, 56, 57 and 58. In the range 100-105, only 102 and 105 are naughty numbers.
Comments
Post a Comment