## UMNOZAK - Umnozak

no tags

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 < 1018), 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.

 Added by: Neal Wu Date: 2008-11-08 Time limit: 1.329s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO Resource: Croatian Olympiad in Informatics 2008