某所大学的数论实验室正在研究正整数的平方与立方的分布之间的关系。

给定一个非负整数 $k$。考虑从 $a$ 到 $b$（含两端）的正整数集合。该集合的 $k$-密度定义为满足 $a \le x^2 \le b$、$a \le y^3 \le b$ 且 $|x^2-y^3| \le k$ 的正整数对 $(x,y)$ 的数量。

例如，从 $1$ 到 $30$ 的正整数集合的 $2$-密度等于 $3$，因为以下数对符合条件：

• $x=1$, $y=1$, $|x^2-y^3|=|1-1|=0$;

• $x=3$, $y=2$, $|x^2-y^3|=|9-8|=1$;

• $x=5$, $y=3$, $|x^2-y^3|=|25-27|=2$.

请编写程序，根据给定的正整数 $a$、$b$ 和非负整数 $k$，求出从 $a$ 到 $b$（含两端）的正整数集合的 $k$-密度。

输入格式

输入包含三行。第一行包含正整数 $a$，第二行包含正整数 $b$，第三行包含非负整数 $k$（$1 \le a \le b \le 10^{18}$，$0 \le k \le 10^{18}$）。

输出格式

输出一个整数：从 $a$ 到 $b$（含两端）的正整数集合的 $k$-密度。

样例

输入格式 1

1
30
2

输出格式 1

3

子任务

只有通过某个子任务及其所依赖的子任务的所有测试，才能获得该子任务的分数。