Boyle's Law

Time limit2sMemory limit128 MB

Summary

Count positive integers N up to 10^18 whose self-product, N times the product of its digits, falls within a given range [A, B].

Level: Hard8 of 10
Topics: Math, Dynamic programming, Number theory, Binary search
Solved: No attempts yet

Problem

The digit product of a positive integer N is the product of all digits in its decimal representation. For instance, the digit product of 2612 is 2 * 6 * 1 * 2 = 24.

The self-product of N is N multiplied by its digit product. Thus the self-product of 2612 is 2612 * 24 = 62688.

Given two integers A and B, count the positive integers N whose self-product is at least A and at most B.

Input

The first line contains two integers A and B. (1 <= A <= B < $10^{18}$ )

Output

Output the number of positive integers whose self-product is between A and B, inclusive.

Hint

The self-products of 19, 24, 32, and 41 are 171, 192, 192, and 164, respectively. Therefore, in the range [145, 192], these four numbers satisfy the condition.

Examples1

Example 1
Input
```
145 192
```
Expected output
```
4
```