Задача C. Квадратная сумма ≡

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня заведующий отделом для проверки одной из гипотез дал Тимофею следующее задание: определить, сколько есть способов выбрать из первых n натуральных чисел два различных числа так, чтобы их сумма являлась квадратом некоторого натурального числа?

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

Единственная строка входного файла содержит натуральное число n.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 100, получат не менее 20 баллов.

Решения, верно работающие при n ≤ 1000, получат не менее 40 баллов.

Пояснение к примеру

В примере дано n = 10. Переберем все возможные пары чисел из диапазона от 1 до 10 и сложим их — в семи случаях получим квадрат.

1 + 3 = 4, 1 + 8 = 9, 2 + 7 = 9, 3 + 6 = 9, 4 + 5 = 9, 6 + 10 = 16 и 7 + 9 = 16.

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

10

7