Equation

Time limit1sMemory limit256 MB

Summary

Count integers n in [a,b] with k times the sum of squared digits of n equal to n, where a and b go up to 10^18.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Brute force, Implementation
Solved: No attempts yet

Problem

For a positive integer $n$ , let $f(n)$ be the sum of the squares of the digits in its decimal representation. Given three integers $k, a, b$ , determine the number of natural numbers $n$ such that $a \le n \le b$ and $n$ satisfies the equation [ k\cdot f(n) = n. ]

Input

The first and only line contains the three integers from the statement: $k, a, b$ ( $1 \le k, a, b \le 10^{18}$ , $a \le b$ ).

Output

Output a single integer: the number of integer solutions of the equation that lie in the range $[a,b]$ .

Hint

In the example, the only positive integers $n$ in the range $[5000,10000]$ that satisfy the equation for $k=51$ are $7293$ , $7854$ and $7905$ .

Examples1

Example 1
Input
```
51 5000 10000
```
Expected output
```
3
```