In the laboratory of number theory of one university, they study the relationship between
distribution of squares and cubes of natural numbers.
Let a non-negative integer k be given. Consider the set of natural
numbers from a to b, inclusive. We will call the k-density of this set the number
pairs of natural numbers x and y such that a ≤ x2 ≤ b, a≤ y3 ≤ b, with |x2– y3| ≤ k.
For example, the 2-density of the set of natural numbers from 1 to 30 is 3 because
the following pairs fit:
x = 1, y = 1, |x2– y3| = |1 – 1| = 0;
x = 3, y = 2, |x2– y3| = |9 – 8| = 1;
x = 5, y = 3, |x2– y3| = |25 – 27| = 2.
It is required to write a program that, given natural numbers a and b, and
also to a non-negative integer k, determines the k-density of the set of naturals
numbers from a to b, inclusive.
Input data format
The input contains three lines. The first line contains a natural number a,
the second line contains a natural number b, the third line contains a non-negative integer
number k (1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018).
Output format
The output should contain a single integer: the desired k-density
sets of natural numbers from a to b, inclusive.