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

Условие

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

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

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

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

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

Ограничения

$5 \le n \le 10^{9}$

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

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

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

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

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

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

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

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

5

1

65

2

1105

4