Description

For a positive integer $n$, define $\operatorname{f}(n)$ as the sum of the squares of its decimal digits.

Now you are given three positive integers $k, a, b$. Find the number of integers $n$ such that $a \le n \le b$ and $k \times \operatorname{f}(n) = n$.

Input Format

The first line contains three positive integers $k, a, b$.

Output Format

Output one integer, the number of integers $n$ that satisfy the condition.

51 5000 10000

3

Hint

For $100\%$ of the testdata, $1 \le k, a, b \le 10^{18}$, and $a \le b$.

Sample Explanation:

The $3$ valid values of $n$ are $7293$, $7854$, and $7905$.

Translated by ChatGPT 5