A university number theory laboratory is studying the relationship between the distribution of squares and cubes of positive integers.

Let $k$ be a nonnegative integer. Consider the set of positive integers from $a$ to $b$, inclusive. Its $k$-density is the number of pairs of positive integers $x$ and $y$ such that $a \le x^2 \le b$, $a \le y^3 \le b$, and $|x^2-y^3| \le k$.

For example, the $2$-density of the set of positive integers from $1$ to $30$ is $3$, since the following pairs qualify:

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

Write a program that, given positive integers $a$ and $b$ and a nonnegative integer $k$, determines the $k$-density of the set of positive integers from $a$ to $b$, inclusive.

Input

The input contains three lines. The first line contains the positive integer $a$, the second contains the positive integer $b$, and the third contains the nonnegative integer $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Output

Output one integer: the required $k$-density of the set of positive integers from $a$ to $b$, inclusive.

Examples

Input 1

1
30
2

Output 1

3

Subtasks

Points for a subtask are awarded only if all tests of that subtask and its prerequisite subtasks are passed.