smithnumbers

Smith numbers were named by Albert Wilansky of Lehigh University. He noticed the property in the phone number (493-7775) of his brother-in-law Harold Smith:
 4937775 = 3 × 5 × 5 × 65837 and (4 + 9 + 3 + 7 + 7 + 7 + 5) = (3)+ (5) + (5) + (6 + 5 + 8 + 3 + 7) = 42.
In simple words, a number is said to be a Smith Number if its digit_sum is equal to the sum of digit_sums_of_all_its_prime_factors.  

Input:
First line contains T which is the number of test cases.
T lines follow each containing two integers L and R.

Output:
For each range L to R (both inclusive), output the number of Smith Numbers in this range.

Constraints:

1 ≤ T ≤ 10^6
2 ≤ L ≤ R ≤ 10^7

Scoring:

1 ≤ T ≤ 1000, 2 ≤ L ≤ R ≤ 10000: (30 pts)
Orginal Constraints : (70 pts)

Note:
Large IO. Use scanf/printf(in C/C++).

SAMPLE INPUT
2
2 3
2 10



SAMPLE OUTPUT
2
5

Explanation

Case 1: In the range 2 to 3, both the numbers are Smith Numbers. As both have just one prime factor, the digitSum thus will be same.
Hence answer is 2.

Case 2: 2,3,4,5,7 are the Smith Numbers in this range. 4 is a Smith Number because 4=2*2 and dgtSum(4)=dgtSum(2)+dgtSum(2). So the answer for this case is 5.

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions: