No laboratório de teoria dos números de uma universidade, estuda-se a relação entre a distribuição dos quadrados e dos cubos dos inteiros positivos.

Seja $k$ um inteiro não negativo. Considere o conjunto dos inteiros positivos de $a$ a $b$, inclusive. A sua densidade de ordem $k$ é o número de pares de inteiros positivos $x,y$ tais que $a \le x^2 \le b$, $a \le y^3 \le b$ e $|x^2-y^3| \le k$.

Por exemplo, a densidade de ordem $2$ do conjunto dos inteiros positivos de $1$ a $30$ é $3$, pois os seguintes pares satisfazem as condições:

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

Escreva um programa que, dados os inteiros positivos $a,b$ e o inteiro não negativo $k$, determine a densidade de ordem $k$ do conjunto dos inteiros positivos de $a$ a $b$, inclusive.

Entrada

A entrada contém três linhas. A primeira contém o inteiro positivo $a$, a segunda o inteiro positivo $b$ e a terceira o inteiro não negativo $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Saída

A saída deve conter um inteiro: a densidade de ordem $k$ pretendida do conjunto dos inteiros positivos de $a$ a $b$, inclusive.

Exemplos

Entrada 1

1
30
2

Saída 1

3

Subtarefas

Os pontos de cada subtarefa são atribuídos apenas se todos os seus testes e os das subtarefas necessárias forem aprovados.