Задача D. Сумма квадратов ≡

Условие

Найдите количество способов представления данного натурального числа в виде суммы двух квадратов различных натуральных чисел. Способы, отличающиеся порядком слагаемых, считаются одинаковыми.

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

В единственной строке входного файла записано одно натуральное число n.

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

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

Ограничения

5 ≤ n ≤ 10⁹

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

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

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

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

Комментарий к первому примеру: существует единственный способ представить 5 в виде суммы двух квадратов: 5 = 2² + 1².

Комментарий ко второму примеру: существует два способа представить 65 в виде суммы двух квадратов: 65 = 8² + 1² = 7² + 4².

Комментарий к третьему примеру: существует четыре способа представить 1105 в виде суммы двух квадратов: 1105 = 33² + 4² = 32² + 9² = 31² + 12² = 24² + 23².

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

5

1

65

2

1105

4