SP3314 UMNOZAK - Umnozak

The digit-product of a positive integer is the product of the number's decimal digits. For example, the digit-product of 2612 is 2 · 6 · 1 · 2 = 24. The self-product of a number is the product of the number and its digit-product. For example, the self-product of 2612 is 2612 · 24 = 62688. Write a program that, given two positive integers A and B (1 ≤ A ≤ B < 10 $ ^{18} $ ), calculates the number of positive integers whose self-product is between A and B, inclusive.

The first line of input contains the integer T (1 ≤ T ≤ 20). The next T lines each contain a pair of integers A and B.

For each test case, print a line with the number of positive integers whose self-product is between A and B.