Задача 2. Квадраты и кубы ≡

Условие

В лаборатории теории чисел одного университета изучают связь между распределением квадратов и кубов натуральных чисел.

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных чисел от a до b, включительно. Будем называть k-плотностью этого множества количество пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x² − y³| ≤ k. Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как подходят следующие пары:

x = 1, y = 1, |x² − y³| = |1 − 1| = 0;

x = 3, y = 2, |x² − y³| = |9 − 8| = 1;

x = 5, y = 3, |x² − y³| = |25 − 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а также целому неотрицательному числу k, определяет k-плотность множества натуральных чисел от a до b, включительно.

Формат входных данных

Входные данные содержат три строки. Первая строка содержит натуральное число a, вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное число k.

Формат выходных данных

Выходные данные должны содержать одно целое число: искомую k-плотность множества натуральных чисел от a до b, включительно.

Ограничения

1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

1
30
2

3