某所大學的數論實驗室正在研究正整數的平方與立方的分布之間的關係。

給定一個非負整數 $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

子任務

只有通過某個子任務及其所依賴的子任務的所有測試，才能獲得該子任務的分數。