ある大学の数論研究室では、正の整数の平方と立方の分布の関係を研究しています。

非負整数 $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$-密度を求めるプログラムを書いてください。

入力

入力は3行です。1行目に正の整数 $a$、2行目に正の整数 $b$、3行目に非負整数 $k$ が与えられます（$1 \le a \le b \le 10^{18}$、$0 \le k \le 10^{18}$）。

出力

$a$ から $b$ まで（両端を含む）の正の整数の集合の $k$-密度を、1つの整数として出力してください。

入出力例

入力 1

1
30
2

出力 1

3

小課題

各小課題の得点は、その小課題と必要な小課題のすべてのテストに合格した場合にのみ与えられます。