Vid ett universitets laboratorium för talteori studeras sambandet mellan fördelningen av kvadrater och kuber av positiva heltal.

Låt $k$ vara ett icke-negativt heltal. Betrakta mängden positiva heltal från $a$ till $b$, inklusive ändpunkterna. Dess $k$-täthet är antalet par av positiva heltal $x,y$ sådana att $a \le x^2 \le b$, $a \le y^3 \le b$ och $|x^2-y^3| \le k$.

Till exempel är $2$-tätheten hos mängden positiva heltal från $1$ till $30$ lika med $3$, eftersom följande par uppfyller villkoren:

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

Skriv ett program som, givet positiva heltal $a,b$ och ett icke-negativt heltal $k$, bestämmer $k$-tätheten hos mängden positiva heltal från $a$ till $b$, inklusive ändpunkterna.

Indata

Indata innehåller tre rader. Den första innehåller det positiva heltalet $a$, den andra det positiva heltalet $b$ och den tredje det icke-negativa heltalet $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Utdata

Utdata ska innehålla ett heltal: den sökta $k$-tätheten hos mängden positiva heltal från $a$ till $b$, inklusive ändpunkterna.

Exempel

Indata 1

1
30
2

Utdata 1

3

Deluppgifter

Poäng för en deluppgift ges endast om alla tester för den och dess nödvändiga deluppgifter klaras.