Le laboratoire de théorie des nombres d’une université étudie la relation entre la répartition des carrés et des cubes des entiers strictement positifs.

Soit $k$ un entier positif ou nul. Considérons l’ensemble des entiers strictement positifs de $a$ à $b$, bornes incluses. Sa densité d’ordre $k$ est le nombre de couples d’entiers strictement positifs $x$ et $y$ tels que $a \le x^2 \le b$, $a \le y^3 \le b$ et $|x^2-y^3| \le k$.

Par exemple, la densité d’ordre $2$ de l’ensemble des entiers strictement positifs de $1$ à $30$ vaut $3$, car les couples suivants conviennent :

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

Écrivez un programme qui, étant donnés les entiers strictement positifs $a,b$ et l’entier positif ou nul $k$, détermine la densité d’ordre $k$ de l’ensemble des entiers strictement positifs de $a$ à $b$, bornes incluses.

Entrée

L’entrée comporte trois lignes. La première contient l’entier strictement positif $a$, la deuxième l’entier strictement positif $b$ et la troisième l’entier positif ou nul $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Sortie

La sortie doit contenir un entier : la densité d’ordre $k$ recherchée de l’ensemble des entiers strictement positifs de $a$ à $b$, bornes incluses.

Exemples

Entrée 1

1
30
2

Sortie 1

3

Sous-tâches

Les points d’une sous-tâche sont attribués uniquement si tous ses tests et ceux des sous-tâches requises sont réussis.