Im Labor für Zahlentheorie einer Universität wird der Zusammenhang zwischen der Verteilung von Quadraten und Kuben positiver ganzer Zahlen untersucht.

Sei $k$ eine nichtnegative ganze Zahl. Betrachten wir die Menge der positiven ganzen Zahlen von $a$ bis $b$, einschließlich beider Grenzen. Ihre $k$-Dichte ist die Anzahl der Paare positiver ganzer Zahlen $x,y$, für die $a \le x^2 \le b$, $a \le y^3 \le b$ und $|x^2-y^3| \le k$ gelten.

Zum Beispiel beträgt die $2$-Dichte der Menge positiver ganzer Zahlen von $1$ bis $30$ genau $3$, da folgende Paare die Bedingungen erfüllen:

• $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$.

Schreibe ein Programm, das für gegebene positive ganze Zahlen $a,b$ und eine nichtnegative ganze Zahl $k$ die $k$-Dichte der Menge positiver ganzer Zahlen von $a$ bis $b$, einschließlich beider Grenzen, bestimmt.

Eingabe

Die Eingabe besteht aus drei Zeilen. Die erste enthält die positive ganze Zahl $a$, die zweite die positive ganze Zahl $b$ und die dritte die nichtnegative ganze Zahl $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Ausgabe

Die Ausgabe soll eine ganze Zahl enthalten: die gesuchte $k$-Dichte der Menge positiver ganzer Zahlen von $a$ bis $b$, einschließlich beider Grenzen.

Beispiele

Eingabe 1

1
30
2

Ausgabe 1

3

Teilaufgaben

Punkte für eine Teilaufgabe werden nur vergeben, wenn alle Tests dieser Teilaufgabe und ihrer erforderlichen Teilaufgaben bestanden wurden.