Một phòng thí nghiệm lý thuyết số của một trường đại học đang nghiên cứu mối quan hệ giữa phân bố các bình phương và lập phương của các số nguyên dương.

Cho số nguyên không âm $k$. Xét tập các số nguyên dương từ $a$ đến $b$, kể cả hai đầu mút. Mật độ bậc $k$ của tập này là số cặp số nguyên dương $x,y$ thỏa mãn $a \le x^2 \le b$, $a \le y^3 \le b$ và $|x^2-y^3| \le k$.

Ví dụ, mật độ bậc $2$ của tập các số nguyên dương từ $1$ đến $30$ bằng $3$, vì các cặp sau thỏa mãn:

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

Hãy viết chương trình nhận các số nguyên dương $a,b$ và số nguyên không âm $k$, rồi xác định mật độ bậc $k$ của tập các số nguyên dương từ $a$ đến $b$, kể cả hai đầu mút.

Dữ liệu vào

Dữ liệu vào gồm ba dòng. Dòng đầu chứa số nguyên dương $a$, dòng thứ hai chứa số nguyên dương $b$, dòng thứ ba chứa số nguyên không âm $k$ ($1 \le a \le b \le 10^{18}$, $0 \le k \le 10^{18}$).

Dữ liệu ra

Xuất một số nguyên: mật độ bậc $k$ cần tìm của tập các số nguyên dương từ $a$ đến $b$, kể cả hai đầu mút.

Ví dụ

Dữ liệu vào 1

1
30
2

Dữ liệu ra 1

3

Nhiệm vụ con

Điểm của mỗi nhiệm vụ con chỉ được trao nếu vượt qua tất cả các kiểm thử của nhiệm vụ đó và các nhiệm vụ con tiên quyết.