Self Product

Time limit3sMemory limit256 MB

Summary
Count positive integers N whose self product (N times the product of its decimal digits) lies within a given range [A,B] with B up to 10^18.
Level

Medium7 of 10

Topics
Math, Number theory, Binary search
Solved
No attempts yet

Problem

For a positive integer N, its digit product is the product of all decimal digits of N. For example, the digit product of 2612 is 2 × 6 × 1 × 2 = 24.

The self product of N is N multiplied by its digit product. Therefore, the self product of 2612 is 2612 × 24 = 62688.

Given two positive integers A and B, count how many positive integers have a self product at least A and at most B.

Input

The first line contains two integers A and B separated by a space.

  • 1 ≤ A ≤ B < 10^18

Output

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

Examples3

  1. Example 1

    Input
    20 30
    Expected output
    2

  2. Example 2

    Input
    145 192
    Expected output
    4

  3. Example 3

    Input
    2224222 2224222
    Expected output
    1