题目描述

译自 ROI 2018 Regional. Day1 T2. Квадраты и кубы

数学家们研究了「自然数的平方的分布」与「自然数的立方的分布」之间的关系。

已知非负整数 $a$, $b$, $k$。考虑集合 $S = {a, a+1, \ldots, b}$，该集合的「$k$ 密度」表示的是 $T$ 中元素的个数，其中 $T = {(x, y) \mid x \in \mathbb{N}, y \in \mathbb{N}, x^2 \in S, y^3 \in S, |x^2 - y^3| \le k}$。请求出 $S$ 的 $k$ 密度。

样例

输入

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$。

数据范围与提示

对于所有数据，$1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$。