Equation

Time limit2sMemory limit512 MB

Summary

Count integers n in [a, b] up to 10^18 with k times the sum of squares of n's decimal digits equal to n.

Level: Hard8 of 10
Topics: Math, Brute force, Dynamic programming, Number theory
Solved: No attempts yet

Problem

For a positive integer $n$ , let $f(n)$ be the sum of the squares of its decimal digits. You are given three positive integers $k, a, b$ . Determine how many positive integers $n$ satisfy $a \le n \le b$ and are solutions of the equation

$k \cdot f(n) = n.$

Input

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

Output

Your program should print one integer: the number of solutions of the equation in the interval $[a, b]$ .

Hint

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

Examples1

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