Colossal Candy Counts

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.

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 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 |