题目描述

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

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

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

样例

input

1
30
2

output

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 ≤ a ≤ b ≤ 10^{18},$ $0 ≤ k ≤ 10^{18}$.