CCSC Mid-South Contest 2019

Start

2019-04-12 18:00 UTC

CCSC Mid-South Contest 2019

End

2019-04-12 22:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -223 days 1:42:56

Time elapsed

4:00:00

Time remaining

0:00:00

Problem C
Colossal Candy Counts

/problems/ccsc19.colossalcandycounts/file/statement/en/img-0001.jpg
Photo of candy, CC0 (public domain).

Colin wants to buy some candy. In fact, he wants to buy a colossal amount of candy, but that doesn’t necessarily mean what you think it does. Colin is obsessed with number theory and has invented a type of number called a colossal number.

An integer $n \geq 0$ is called colossal if there exist integers $a,b \geq 0$ such that $a^ b = n$, and the sum of the base-$10$ digits of $n$ is equal to $a$. For example, $512$ is colossal since $8^3 = 512$ and $5 + 1 + 2 = 8$.

Given the minimum and maximum amounts of candy Colin is willing to buy, he needs your help figuring out how many different choices he has if he wants to buy a colossal amount.

Input

The input consists of two space-separated integers, $c_ L$ and $c_ H$, such that $0 \leq c_ L \leq c_ H \leq 10^{12}$.

Output

Output a single line containing the number of colossal integers $c$ in the interval $c_ L \leq c \leq c_ H$.

Sample Input 1 Sample Output 1
15 5000
4
Sample Input 2 Sample Output 2
512 512
1