Il laboratorio di teoria dei numeri di un’università studia la relazione tra la distribuzione dei quadrati e dei cubi degli interi positivi.

Sia $k$ un intero non negativo. Consideriamo l’insieme degli interi positivi da $a$ a $b$, estremi inclusi. La sua densità di ordine $k$ è il numero di coppie di interi positivi $x,y$ tali che $a \le x^2 \le b$, $a \le y^3 \le b$ e $|x^2-y^3| \le k$.

Ad esempio, la densità di ordine $2$ dell’insieme degli interi positivi da $1$ a $30$ è $3$, poiché le seguenti coppie soddisfano le condizioni:

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

Scrivi un programma che, dati gli interi positivi $a,b$ e l’intero non negativo $k$, determini la densità di ordine $k$ dell’insieme degli interi positivi da $a$ a $b$, estremi inclusi.

Input

L’input contiene tre righe. La prima contiene l’intero positivo $a$, la seconda l’intero positivo $b$ e la terza l’intero non negativo $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Output

L’output deve contenere un intero: la densità di ordine $k$ richiesta dell’insieme degli interi positivi da $a$ a $b$, estremi inclusi.

Esempi

Input 1

1
30
2

Output 1

3

Sottoproblemi

I punti di ogni sottoproblema vengono assegnati solo se sono superati tutti i suoi test e quelli dei sottoproblemi necessari.