어느 대학의 정수론 연구실에서는 양의 정수의 제곱과 세제곱의 분포 사이의 관계를 연구하고 있습니다.

음이 아닌 정수 $k$가 주어집니다. $a$부터 $b$까지 양 끝을 포함하는 양의 정수 집합을 생각합시다. 이 집합의 $k$-밀도는 $a \le x^2 \le b$, $a \le y^3 \le b$, $|x^2-y^3| \le k$를 만족하는 양의 정수 쌍 $(x,y)$의 개수입니다.

예를 들어 $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$-밀도를 출력해야 합니다.

예제

입력 1

1
30
2

출력 1

3

서브태스크

각 서브태스크의 점수는 해당 서브태스크와 필요한 서브태스크의 모든 테스트를 통과한 경우에만 주어집니다.