For a natural number $n$, let $f(n)$ denote the sum of the squares of its digits in decimal representation. You are given three natural numbers $k, a, b$. Your task is to determine the number of such natural numbers $n$ that $a \le n \le b$ and $n$ is a solution to the equation $$k \cdot f(n) = n.$$

Input

The first and only line of input contains three integers: $k, a, b$, where $1 \le k, a, b \le 10^{18}$ and $a \le b$.

Output

Your program should output a single integer representing the number of solutions to the equation in the interval $[a, b]$.

Examples

Input 1

51 5000 10000

Output 1

3

Note

The only natural numbers $n$ in the interval $[5000, 10000]$ satisfying the equation for $k = 51$ are $7293$, $7854$, and $7905$.