제곱과 세제곱

어느 대학의 정수론 연구실에서는 자연수의 제곱과 세제곱의 분포 사이의 관계를 연구한다.

음이 아닌 정수 $k$가 주어졌다고 하자. $a$부터 $b$까지의 자연수 전체, 양 끝을 포함하는 집합을 생각하자. 이 집합의 k-밀도를 다음과 같이 정의한다. 자연수 $x$와 $y$의 쌍 중에서 $a \le x^2 \le b$, $a \le y^3 \le b$이고 $|x^2 - y^3| \le k$인 쌍의 개수이다.

예를 들어 1부터 30까지의 자연수 집합의 2-밀도는 3이다. 다음 쌍들이 조건을 만족하기 때문이다.

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

자연수 $a$와 $b$, 음이 아닌 정수 $k$가 주어질 때 $a$부터 $b$까지의 자연수 전체, 양 끝을 포함하는 집합의 k-밀도를 구하는 프로그램을 작성하라.

입력은 세 줄로 이루어진다. 첫째 줄에는 자연수 $a$, 둘째 줄에는 자연수 $b$, 셋째 줄에는 음이 아닌 정수 $k$가 주어진다 ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

첫째 줄에 $a$부터 $b$까지의 자연수 전체, 양 끝을 포함하는 집합의 k-밀도를 나타내는 정수 하나를 출력한다.