W laboratorium teorii liczb pewnego uniwersytetu bada się związek między rozkładem kwadratów i sześcianów dodatnich liczb całkowitych.

Niech $k$ będzie nieujemną liczbą całkowitą. Rozważmy zbiór dodatnich liczb całkowitych od $a$ do $b$ włącznie. Jego $k$-gęstością nazywamy liczbę par dodatnich liczb całkowitych $x,y$ takich, że $a \le x^2 \le b$, $a \le y^3 \le b$ oraz $|x^2-y^3| \le k$.

Na przykład $2$-gęstość zbioru dodatnich liczb całkowitych od $1$ do $30$ wynosi $3$, ponieważ warunki spełniają następujące pary:

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

Napisz program, który dla danych dodatnich liczb całkowitych $a,b$ i nieujemnej liczby całkowitej $k$ wyznaczy $k$-gęstość zbioru dodatnich liczb całkowitych od $a$ do $b$ włącznie.

Wejście

Wejście zawiera trzy wiersze. Pierwszy zawiera dodatnią liczbę całkowitą $a$, drugi dodatnią liczbę całkowitą $b$, a trzeci nieujemną liczbę całkowitą $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Wyjście

Wyjście powinno zawierać jedną liczbę całkowitą: szukaną $k$-gęstość zbioru dodatnich liczb całkowitych od $a$ do $b$ włącznie.

Przykład

Wejście 1

1
30
2

Wyjście 1

3

Podzadania

Punkty za podzadanie przyznaje się tylko po zaliczeniu wszystkich jego testów oraz testów wymaganych podzadań.