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⁶
• 2 ≤ L ≤ R ≤ 10⁷

Scoring:

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

Note:

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