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¹⁸), calculates the number of positive integers whose self-product is between A and B, inclusive.

Input

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.

Output

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

Example

Input:
3
20 30
145 192
2224222 2224222

Output:
2
4
1

For the second example, the self-products of the numbers 19, 24, 32, and 41 are 171, 192, 192 and 164, respectively.