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 ≤ 106
- 2 ≤ L ≤ R ≤ 107
Scoring:
- 1 ≤ T ≤ 1000, 2 ≤ L ≤ R ≤ 10000: (30 pts)
- Orginal Constraints : (70 pts)
Note:
Large IO. Use scanf/printf(in C/C++).
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.
