Cho ba số nguyên dương ~a~, ~b~, ~k~. Hai số nguyên dương ~x~, ~y~ được gọi là một cặp số đặc biệt nếu cả ba điều kiện sau cùng đúng:

• ~a \le x^2 \le b~;
• ~a \le y^3 \le b~;
• ~|x^2 - y^3| \le k~.

Yêu cầu: Đếm số cặp số đặc biệt ~(x, y)~.

Dữ liệu

Một dòng duy nhất gồm ba số nguyên dương ~a~, ~b~, ~k~ (~1 \le a \le b \le 10^{18}~, ~1 \le k \le 10^{18}~).

Kết quả

In ra một số nguyên là số cặp số đặc biệt.

Ví dụ

CAPSO.INP

1 30 2

CAPSO.OUT

3

Giải thích: Các cặp số đặc biệt là ~(1, 1)~, ~(3, 2)~, ~(5, 3)~.

Giới hạn

• Subtask 1 (30% số điểm): ~b \le 1000~.
• Subtask 2 (20% số điểm): ~b \le 10^6~.
• Subtask 3 (20% số điểm): ~b \le 10^{12}~.
• Subtask 4 (30% số điểm): không có ràng buộc gì thêm.