[AdditionalFile5280.zip](file://AdditionalFile5280.zip?type=additional_file)

#5280. 「PA 2015」Równanie

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Runda próbna zwykła Równanie

对于自然数 $n$，我们用 $f(n)$ 表示其十进制表示中各位数字的平方和。给定三个自然数 $k, a, b$，你的任务是计算满足 $a \leq n \leq b$ 且 $n$ 是以下方程解的自然数 $n$ 的数量：

输入格式

输入的唯一一行包含三个整数 $k, a, b$ $(1 \leq k, a, b \leq 10^{18}, a \leq b)$，如题目描述中所示。

输出格式

你的程序应输出一个整数，表示区间 $[a, b]$ 内满足任务描述中方程的解的数量。

样例

输入

51 5000 10000

输出

3

在区间 $[5000, 10000]$ 内，满足 $k=5$ 的方程的自然数只有 $7293$、$7854$ 和 $7905$。