题目描述

译自 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$ 密度。

输入格式

输入包含三行，分别为 $a,b,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 ≤ a ≤ b ≤ 10^{18},$ $0 ≤ k ≤ 10^{18}$.