Description

Define the digit product of a positive integer as the result of multiplying all of its digits. For example:

The digit product of $2612$ is: $2\times 6\times 1\times 2=24$.

Define the self-product of a positive integer as the result of multiplying the number by its digit product. For example:

The self-product of $2612$ is: $2612\times 24=62688$.

Given two integers $A,B$, find the number of positive integers whose self-product lies in the interval $[A,B]$.

Input Format

Input one line containing two integers $A,B$.

Output Format

Output one line containing one integer, indicating how many positive integers have their self-product within the interval $[A,B]$.

20 30

2

145 192

4

2224222 2224222

1

Hint

Explanation for Sample 2

There are $19,24,32,41$ that satisfy the requirement. Their self-products are $171,192,192,164$, respectively.

Constraints

• For $25\%$ of the testdata, $A\le B\le 10^8$;
• For another $15\%$ of the testdata, $A\le B\le 10^{12}$;
• For $100\%$ of the testdata, $1\le A\le B< 10^{18}$.

Notes

This problem is translated from COCI2007-2008 COI2008 T4 UMNOZAK。

Translated by ChatGPT 5